Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels

Preprint English OPEN
Havemann, Frank ; Heinz, Michael ; Struck, Alexander ; Gläser, Jochen (2010)
  • Related identifiers: doi: 10.1088/1742-5468/2011/01/P01023
  • Subject: Physics - Data Analysis, Statistics and Probability | Computer Science - Social and Information Networks | Physics - Physics and Society | H.2.8

We propose a new local, deterministic and parameter-free algorithm that detects fuzzy and crisp overlapping communities in a weighted network and simultaneously reveals their hierarchy. Using a local fitness function, the algorithm greedily expands natural communities of seeds until the whole graph is covered. The hierarchy of communities is obtained analytically by calculating resolution levels at which communities grow rather than numerically by testing different resolution levels. This analytic procedure is not only more exact than its numerical alternatives such as LFM and GCE but also much faster. Critical resolution levels can be identified by searching for intervals in which large changes of the resolution do not lead to growth of communities. We tested our algorithm on benchmark graphs and on a network of 492 papers in information science. Combined with a specific post-processing, the algorithm gives much more precise results on LFR benchmarks with high overlap compared to other algorithms and performs very similar to GCE.
  • References (14)
    14 references, page 1 of 2

    [1] G. Palla, I. Derenyi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814{818, 2005. arXiv:physics.socph/0506133.

    [2] J. Baumes, M. Goldberg, and M. Magdon-Ismail. E cient identi cation of overlapping communities. Intelligence and Security Informatics, 3495:27{36, 2005.

    [3] X. Wang, L. Jiao, and J. Wu. Adjusting from disjoint to overlapping community detection of complex networks. Physica A: Statistical Mechanics and its Applications, 388(24):5045{5056, 2009.

    [4] Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann. Link communities reveal multi-scale complexity in networks. Nature, 466:761{764, 2010. arXiv:physics.soc-ph/0903.3178.

    [5] T.S. Evans and R. Lambiotte. Edge Partitions and Overlapping Communities in Complex Networks. European Physical Journal B, 77:265{272, 2009. arXiv:physics.data-an/0912.4389.

    [6] A. Lancichinetti, S. Fortunato, and J. Kertesz. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11:033015, 2009. arXiv:physics.soc-ph/0802.1218.

    [7] C. Lee, F. Reid, A. McDaid, and N. Hurley. Detecting highly overlapping community structure by greedy clique expansion. In Proceedings of the 4th SNA-KDD Workshop, 2010. arXiv:physics.data-an/1002.1827v2.

    [8] F. Havemann, M. Heinz, A. Struck, and J. Glaser. Identi cation of overlapping communities by locally calculating community-changing resolution levels. Poster at ASONAM conference, Odense, Denmark, August 2010, arXiv:physics.data-an/1008.1004, 2010.

    [9] S. Gregory. Fuzzy overlapping communities in networks. arXiv:physics.soc-ph/1010.1523, 2010.

    [10] W.W. Zachary. An information ow model for con ict and ssion in small groups. Journal of Anthropological Research, 33(4):452{473, 1977.

  • Metrics
    No metrics available
Share - Bookmark