Dynamic Community Detection in Networks with Edge Noise

• Activity Number: 39
• Type: Contributed
• Date/Time: Sunday, July 29, 2012 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): Weston Viles*+ and Eric D Kolaczyk and Mark Kramer
• Companies: Boston University and Boston University and Boston University
• Keywords: Dynamic Network ; Community Detection ; Edge Noise

Abstract

Dynamic networks have emerged as a powerful tool for representing the evolution of relational data. Important to network analysis is the unsupervised detection of network communities, often realized as a cohesive subset of vertices that are unusually well connected among themselves relative to the entire network. Static network community detection is well-studied but, to better understand the life of communities (e.g. birth, merging, splitting, and death) in a dynamic network, one requires more sophisticated tools than those of static network detection.

Existing network detection methods are (i) unable to account for the edge noise (e.g. false positive/negative edge status) that is inherently present in inferred networks and (ii) to discover dynamic communities either, in an ad-hoc manner, sew together discovered static communities or use an implicit notion of community (e.g. by optimizing some criterion). We develop a dynamic community extraction algorithm designed to incorporate two novel capabilities, (i) to directly account for edge noise and (ii) to detect dynamic communities based on an explicit notion that communities are aggregations of smaller motifs.