Communicability graph and community structures in complex networks
Estrada, E. and Hatano, N. and , Institute of Industrial Science, University of Tokyo (Funder) and , New Professors Fund University of Strathclyde (Funder) (2009) Communicability graph and community structures in complex networks. Applied Mathematics and Computation, 214 (2). pp. 500511. ISSN 00963003

PDF (strathprints014296.pdf)
strathprints014296.pdf Download (592kB)  Preview 
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 allclique 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 wellknown algorithm groups all but two of the continental airports into one community.
Item type:  Article 

ID code:  14296 
Keywords:  graph spectrum, complex networks, communicability, network communities, bronkerbosch algorithm, allcliques problem, Mathematics, Computational Mathematics, Applied Mathematics 
Subjects:  Science > Mathematics 
Department:  Faculty of Science > Mathematics and Statistics 
Depositing user:  Mrs Carolynne Westwood 
Date Deposited:  22 Jan 2010 13:20 
Last modified:  30 Apr 2016 10:19 
URI:  http://strathprints.strath.ac.uk/id/eprint/14296 