LinkBlackHole**: Robust Overlapping Community Detection Using Link Embedding

Jungeun Kim, Sungsu Lim, Jae-Gil Lee, Byung Suk Lee

Abstract

This paper proposes LinkBlackHole$^{*}$*, a novel algorithm for finding communities that are (i) overlapping in nodes and (ii) mixing (not separating clearly) in links. There has been a small body of work in each category, but this paper is the first one that addresses both. LinkBlackHole$^{*}$* is a merger of our earlier two algorithms, LinkSCAN$^{*}$* and BlackHole, inheriting their advantages in support of highly-mixed overlapping communities. The former is used to handle overlapping nodes, and the latter to handle mixing links in finding communities. Like LinkSCAN and its more efficient variant LinkSCAN$^{*}$*, this paper presents LinkBlackHole and its more efficient variant LinkBlackHole$^{*}$*, which reduces the number of links through random sampling. Thorough experiments show superior quality of the communities detected by LinkBlackHole$^{*}$* and LinkBlackHole to those detected by other state-of-the-art algorithms. In addition, LinkBlackHole$^{*}$* shows high resilience to the link sampling effect, and its running time scales up almost linearly with the number of links in a network.
BibTeX
@article{kim2019linkblackhole,
  author = {Jungeun Kim and Sungsu Lim and Jae-Gil Lee and Byung Suk Lee},
  title = {{LinkBlackHole**: Robust Overlapping Community Detection Using Link Embedding}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2019},
  doi = {10.1109/tkde.2018.2873750},
}

Loading related content...

Figure