Overlapping Communities via k-Connected Ego Centered Groups

Orman G. K., Karadeli O., Calisir E.

IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Paris, France, 25 - 28 August 2015, pp.1598-1599 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1145/2808797.2809351
  • City: Paris
  • Country: France
  • Page Numbers: pp.1598-1599
  • Galatasaray University Affiliated: Yes


Overlapping community detection allows placing one node to multiple communities. Up to now, many algorithms are proposed for this issue. However, their accuracy depends on the overlapping level of the structure. In this work, we aim at finding relatively small overlapping communities independently than their overlapping level. We define k-connected node groups as cohesive groups in which each pair of nodes has at least k different node disjoint paths from one to another. We propose the algorithm EMOC first finding k-connected groups from the perspective of each node and second merging them to detect overlapping communities. We evaluate the accuracy of EMOC on artificial networks by comparing its results with foremost algorithms. The results indicate that EMOC can find small overlapping communities at any overlapping level. Results on real-world network show that EMOC finds relatively small but consistent communities.