Detecting highly overlapping community structure by greedy clique expansion

Preprint, Conference object English OPEN
Lee, Conrad ; McDaid, Aaron ; Reid, Fergal ; Hurley, Neil J. (2010)
  • Subject: Computer algorithms | Database management | Physics - Data Analysis, Statistics and Probability | Physics - Physics and Society | Social networks | Overlapping | Local custering algorithm | Online social networks | H.2.8 | Complex networks | Community Assignment

In complex networks it is common for each node to belong to several communities, implying a highly overlapping community structure. Recent advances in benchmarking indicate that existing community assignment algorithms that are capable of detecting overlapping communities perform well only when the extent of community overlap is kept to modest levels. To overcome this limitation, we introduce a new community assignment algorithm called Greedy Clique Expansion (GCE). The algorithm identifies distinct cliques as seeds and expands these seeds by greedily optimizing a local fitness function. We perform extensive benchmarks on synthetic data to demonstrate that GCE's good performance is robust across diverse graph topologies. Significantly, GCE is the only algorithm to perform well on these synthetic graphs, in which every node belongs to multiple communities. Furthermore, when put to the task of identifying functional modules in protein interaction data, and college dorm assignments in Facebook friendship data, we find that GCE performs competitively.
  • References (36)
    36 references, page 1 of 4

    [1] Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75-174, 2010. ISSN 0370-1573.

    [2] M. Girvan and M.E.J. Newman. Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA, 99 (12):7821, 2002.

    [3] A. Lancichinetti and S. Fortunato. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E, 80(1): 16118, 2009.

    [4] Andrea Lancichinetti and Santo Fortunato. Community detection algorithms: A comparative analysis. Phys. Rev. E, 80 (5):056117, Nov 2009.

    [5] S. Gregory. Finding overlapping communities in networks by label propagation. Arxiv preprint arXiv:0910.5516, 2009.

    [6] Facebook Press Room. Facebook statistics, February 2009. URL http://www.facebook.com/press/ info.php?statistics.

    [7] Cameron Marlow, Lee Byron, Tom Lento, and Itamar Rosenn. Maintained relationships on facebook, March 2009. URL http://overstated.net/2009/03/09/ maintained-relationships-on-facebook.

    [8] E.N. Sawardecker, M. Sales-Pardo, and L.A.N. Amaral. Detection of node group membership in networks with group overlap. Euro. Phys. Journ. B, 67(3):277-284, 2009.

    [9] G. Palla, I. Derenyi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435:814-818, 2005.

    [10] A. Clauset. Finding local community structure in networks. Phys. Rev. E, 72(2):26132, 2005.

  • Similar Research Results (1)
  • Bioentities (2)
    1gce Protein Data Bank
    2for Protein Data Bank
  • Metrics
    No metrics available
Share - Bookmark