Detecting highly overlapping community structure by greedy clique expansion

Files in This Item:
File Description SizeFormat 
1002.1827v2801.79 kBAdobe PDFDownload
Title: Detecting highly overlapping community structure by greedy clique expansion
Authors: Lee, Conrad
McDaid, Aaron
Reid, Fergal
Hurley, Neil J.
Permanent link:
Date: 25-Jul-2010
Abstract: In complex networks it is common for each node to belong to several communities, implying a highly overlapping community structure. Recent advances in benchmarking indicate that existing community assignment algorithms that are capable of detecting overlapping communities perform well only when the extent of community overlap is kept to modest levels. To overcome this limitation, we introduce a new community assignment algorithm called Greedy Clique Expansion (GCE). The algorithm identifies distinct cliques as seeds and expands these seeds by greedily optimizing a local fitness function. We perform extensive benchmarks on synthetic data to demonstrate that GCE's good performance is robust across diverse graph topologies. Significantly, GCE is the only algorithm to perform well on these synthetic graphs, in which every node belongs to multiple communities. Furthermore, when put to the task of identifying functional modules in protein interaction data, and college dorm assignments in Facebook friendship data, we find that GCE performs competitively.
Funding Details: Science Foundation Ireland
Type of material: Conference Publication
Keywords: Community AssignmentSocial networksOverlappingLocal custering algorithmComplex networks
Subject LCSH: Database management
Computer algorithms
Online social networks
Language: en
Status of Item: Peer reviewed
Conference Details: Paper presented at the 4th SNA-KDD Workshop ’10 (SNA-KDD’10), held in conjunction with The 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2010), July 25, 2010, Washington, DC USA
Appears in Collections:Computer Science Research Collection
Clique Research Collection
CASL Research Collection

Show full item record

Google ScholarTM


This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.