Abstract
Natural arising and evolution of community structures in natural and social networks has been explained as a result of topological relationships among nodes in the same network, and many studies in this field have revealed that it is possible to derive information about the community decomposition of a network just by examining its structure. The most used metric for this kind of analysis is the so-called “modularity” [12][11], which expresses the quality of a candidate community decomposition of a network. Despite its popularity, modularity is hard to be optimized [2] and algorithms for communities discovering based on modularity optimization are practically unfeasible for large networks. On the other hand, methods for community uncovering based on locally evaluated metric are very fast [7]. In this paper we propose the use of a parallel implementation of the local metric based method for community discovering proposed in [9] and the use of the overlapping modularity function [13] to evaluate the best partition. All measures reported in this paper are obtained running our implementation within a grid computing environment.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albert, R., Barabasi, A.-L.: Statistical mechanics of complex networks. Reviews of Modern Physics 74, 47 (2002)
Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., Wagner, D.: On modularity clustering. IEEE Transactions on Knowledge and Data Engineering 20(2), 172–188 (2008)
Carchiolo, V., Malgeri, M., Mangioni, G., Nicosia, V.: Using genetic algorithms to discover overlapping communities in complex networks. In: 10th Experimental Chaos Conference (2008)
Danon, L., Duch, J., Diaz-Guilera, A., Arenas, A.: Comparing community structure identification (2005)
Job Description Language Attributes Specification for the gLite Middlewarem, http://edms.cern.ch/file/590869/1/egee-jra1-tec-590869-jdl-attributes-v0-8.pdf
Fortunato, S., Barthelemy, M.: Resolution limit in community detection. Proc. Natl. Acad. Sci. USA 104, 36 (2007)
Fortunato, S., Castellano, C.: Community Structure in Graphs. In: Encyclopedia of Complexity and System Science. Springer, Heidelberg (2008)
gLite Lightweight Middleware for Grid Computing, http://glite.web.cern.ch/glite/
Lancichinetti, A., Fortunato, S., Kertesz, J.: Detecting the overlapping and hierarchical community structure of complex networks (2008), http://www.citebase.org/abstract?id=oai:arXiv.org:0802.1218
Newman, M.E.J.: The structure and function of complex networks. SIAM Review 45, 167 (2003)
Newman, M.E.J.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. USA 103, 8577 (2006)
Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Physical Review E 69, 026113 (2004)
Nicosia, V., Mangioni, G., Carchiolo, V., Malgeri, M.: Extending modularity definition for directed graphs with overlapping communities (2008) arXiv:0801.1647v3
Zachary, W.W.: An information flow model for conflict and fission in small groups. Journal of Anthropological Research 33, 452–473 (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Fiumicello, D., Longheu, A., Mangioni, G. (2009). Discovering Community Structure on Large Networks Using a Grid Computing Environment. In: Fortunato, S., Mangioni, G., Menezes, R., Nicosia, V. (eds) Complex Networks. Studies in Computational Intelligence, vol 207. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01206-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-01206-8_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01205-1
Online ISBN: 978-3-642-01206-8
eBook Packages: EngineeringEngineering (R0)