Journal Press India^®

Author Details ( * ) denotes Corresponding author

A lot of phenomenon, real world and otherwise can be conveniently represented as graphs, with the nodes corresponding to the entities and the edges representing the interaction be- tween those entities. Communities or modules, which are groups of nodes densely connected to each other within the community but sparsely linked to other communities and the rest of the graph, often having similar structural and functional properties. A lot of algorithms have been proposed to partition the set of vertices into communities; such a partition exclusively puts a node into one community or the other. But in real life a node can belong to multiple communities simultaneously, i.e. the communities can overlap. Different metrics have been proposed. We reduce the modularity maximization problem for splitting the graph into two communities to the MAX-CUT problem with both positive and negative weights. We introduce and analyze three approximation algorithms to maximize modularity for the two community case; recursive bi-partitioning can be carried out as long as modularity increases to split into more than two communities.

Keywords

Modularity MAX-CUT Chromosome

1. D. J. Watts, S. H. Strogatz, Collective dynamics of small-world networks, Nature, 393(6684), 440-442, 1998


2. M. Girvan, M. E. Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences of the United States of America, 99(12), 2002, 7821-7826


3. Detecting community structure in networks, M. E. J. Newman, Eur. Phys. J. B 38,321-330, 2004


4. Using Correspondence Analysis for Joint Displays for Affiliation Networks. Models and Methods in Social Network Analysis. K Faust, Chapter 7 (Cambridge University Press, New York, 2005).


5. J. Scott, Social Network Analysis: A Handbook. Sage, London, 2nd edition.


6. F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, D. Parisi, Defining and identifying communities in networks. Proc. Natl. Acad. Sci. USA 101, 2658-2663, 2004


7. G. W. Flake, S. R. Lawrence, C. L. Giles, F. M. Coetzee, Self-organization and identification of Web communities. IEEE Computer 35, 66-71, 2002


8. L. Danon, J. Duch, A. Diaz-Guilera, A. Arenas, 2005, J. Stat. Mech., P09008


9. Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N.and Barabasi, A.-L. (2000) Nature(London) 407, 651-654.


10. D. A. Fell, A. Wagner, 2000, Nat. Biotechnol. 18, 1121-1122