[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A flexible multiscale approach to overlapping community detection

  • Original Article
  • Published:
Social Network Analysis and Mining Aims and scope Submit manuscript

Abstract

In this work, we develop a flexible methodology for detecting specific notions of community, with a focus on overlapping communities in social networks. Because the word “community” is an ambiguous term, it is necessary to quantify what it means to be a community within the context of a particular type of problem. Our interpretation is that this quantification should be done at a minimum of three scales. These scales are at the level of: individual nodes, individual communities, and the network as a whole. Each of these scales involves quantitative features of community structure that are not accurately represented at the other scales, but are important for defining a particular notion of community. We exemplify sensible ways to quantify what is desired at each of these scales for a notion of community applicable to social networks, and use these models to develop a prototypical community detection algorithm. Some appealing features of the resulting method are that it naturally allows for nodes to belong to multiple communities, and is computationally efficient for large networks with low overall edge density. The scaling of the algorithm is \(O(N\overline{k^2} + \overline{N_{\rm com}^2})\), where N is the number of nodes in the network, \(\overline{N_{\rm com}^2}\) is the average squared community size, and \(\overline{k^2}\) is the expected value of a node’s degree squared.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26
Fig. 27
Fig. 28
Fig. 29
Fig. 30

Similar content being viewed by others

Notes

  1. http://www.cpc.unc.edu/projects/addhealth/.

References

  • Amelio A, Pizzuti C (2014) Overlapping community discovery methods: a survey. In: Social networks: analysis and case studies. Springer, Vienna, pp 105–125

  • Auffarth B (2007) Spectral graph clustering. Universitat de Barcelona, course report for Technicas Avanzadas de Aprendizaj, at Universitat Politecnica de Catalunya

  • Brand M, Huang K (2003) A unifying theorem for spectral embedding and clustering. In: Proceedings of the ninth international workshop on artificial intelligence and statistics

  • Danon L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech 2005(09):P09008

    Article  Google Scholar 

  • Evans TS, Lambiotte R (2009) Line graphs, link partitions, and overlapping communities. Phys Rev E 80(1):016105

    Article  Google Scholar 

  • Fortunato S (2010) Community detection in graphs. Phys Rep 486(3):75–174

    Article  MathSciNet  Google Scholar 

  • Girvan M, Newman MEJ (2001) Community structure in social and biological networks. arXiv preprint cond-mat/0112110

  • Hric D, Darst RK, Fortunato S (2014) Community detection in networks: structural communities versus ground truth. Phys Rev E 90(6):062805

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Lancichinetti A, Fortunato S (2009) Community detection algorithms: a comparative analysis. Phys Rev E 80(5):056117

    Article  Google Scholar 

  • Lancichinetti A, Fortunato S, Kertész J (2009) Detecting the overlapping and hierarchical community structure in complex networks. New J Phys 11(3):033015

    Article  Google Scholar 

  • Palla G, Derényi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043):814–818

    Article  Google Scholar 

  • Pool S, Bonchi F, van Leeuwen M (2014) Description-driven community detection. ACM Trans Intell Syst Technol 5(3):28

    Google Scholar 

  • Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76(3):036106

    Article  Google Scholar 

  • Rees BS, Gallagher KB (2010). Overlapping community detection by collective friendship group inference. In: IEEE international conference on advances in social networks analysis and mining (ASONAM), pp 375–379

  • Rees BS, Gallagher KB (2012) Overlapping community detection using a community optimized graph swarm. Soc Netw Anal Min 2(4):405–417

    Article  Google Scholar 

  • Shen H-W, Cheng X-Q (2010) Spectral methods for the detection of network community structure: a comparative analysis. J Stat Mech 2010(10):P10020

    Article  Google Scholar 

  • Wilson JD, Wang S, Mucha PJ, Bhamidi S, Nobel AB (2014) Nobel A testing based extraction algorithm for identifying significant communities in networks. Ann Appl Stat 8(3):1853–1891

    Article  MATH  MathSciNet  Google Scholar 

  • Xie J, Kelley S, Szymanski BK (2013) Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput Surv 45(4):43

    Article  Google Scholar 

  • Zachary W (1977) An information flow modelfor conflict and fission in small groups1. J Anthropol Res 33(4):452–473

    Google Scholar 

Download references

Acknowledgments

The authors are grateful to the anonymous reviewers (especially one of them) for their insightful comments and suggestions that greatly improved the content and presentation of this manuscript.

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, University of Colorado, Boulder, CO, USA

    M. Brutz

  2. Department of Electrical Engineering, University of Colorado, Boulder, CO, USA

    F. G. Meyer

Authors
  1. M. Brutz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. F. G. Meyer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Brutz.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Brutz, M., Meyer, F.G. A flexible multiscale approach to overlapping community detection. Soc. Netw. Anal. Min. 5, 23 (2015). https://doi.org/10.1007/s13278-015-0259-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s13278-015-0259-z

Keywords

Search

Navigation