Communicability Graph and Community Structures in Complex Networks
Authors:
Preprint
Abstract
We use the concept of the network communicability (Phys. Rev. E 77 (2008) 036111) to define communities in a complex network. The communities are defined as the cliques of a communicability graph, which has the same set of nodes as the complex network and links determined by the communicability function. Then, the problem of finding the network communities is transformed to an all-clique problem of the communicability graph. We discuss the efficiency of this algorithm of community detection. In addition, we extend here the concept of the communicability to account for the strength of the interactions between the nodes by using the concept of inverse temperature of the network. Finally, we develop an algorithm to manage the different degrees of overlapping between the communities in a complex network. We then analyze the USA airport network, for which we successfully detect two big communities of the eastern airports and of the western/central airports as well as two bridging central communities. In striking contrast, a well-known algorithm groups all but two of the continental airports into one community.Keywords
All Related Versions
- Version 1, 2009-05-26, ArXiv
- Published version: Applied Mathematics and Computation, 214 (2), 500.
This publication has 14 references indexed in Scilit:
- A survey of kernel and spectral methods for clusteringPattern Recognition, 2008
- A very fast algorithm for detecting community structures in complex networksPhysica A: Statistical Mechanics and its Applications, 2007
- The worst-case time complexity for generating all maximal cliques and computational experimentsTheoretical Computer Science, 2006
- Comparing community structure identificationJournal of Statistical Mechanics: Theory and Experiment, 2005
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Functional cartography of complex metabolic networksNature, 2005
- Community structure in social and biological networksProceedings of the National Academy of Sciences, 2002
- Enumerating all connected maximal common subgraphs in two graphsTheoretical Computer Science, 2001
- An Information Flow Model for Conflict and Fission in Small GroupsJournal of Anthropological Research, 1977
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970