Overlapping Community Detection Using Neighborhood-Inflated Seed Expansion

Cited 158 time in webofscience Cited 176 time in scopus
  • Hit : 278
  • Download : 0
Community detection is an important task in network analysis. A community ( also referred to as a cluster) is a set of cohesive vertices that have more connections inside the set than outside. In many social and information networks, these communities naturally overlap. For instance, in a social network, each vertex in a graph corresponds to an individual who usually participates in multiple communities. In this paper, we propose an efficient overlapping community detection algorithm using a seed expansion approach. The key idea of our algorithm is to find good seeds, and then greedily expand these seeds based on a community metric. Within this seed expansion method, we investigate the problem of how to determine good seed nodes in a graph. In particular, we develop new seeding strategies for a personalized PageRank clustering scheme that optimizes the conductance community score. An important step in our method is the neighborhood inflation step where seeds are modified to represent their entire vertex neighborhood. Experimental results show that our seed expansion algorithm outperforms other state-of-the-art overlapping community detection methods in terms of producing cohesive clusters and identifying ground-truth communities. We also show that our new seeding strategies are better than existing strategies, and are thus effective in finding good overlapping communities in real-world networks.
Publisher
IEEE COMPUTER SOC
Issue Date
2016-05
Language
English
Article Type
Article
Citation

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, v.28, no.5, pp.1272 - 1284

ISSN
1041-4347
DOI
10.1109/TKDE.2016.2518687
URI
http://hdl.handle.net/10203/275338
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 158 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0