Dynamic social community detection and its applications

PLoS One. 2014 Apr 10;9(4):e91431. doi: 10.1371/journal.pone.0091431. eCollection 2014.

Abstract

Community structure is one of the most commonly observed features of Online Social Networks (OSNs) in reality. The knowledge of this feature is of great advantage: it not only provides helpful insights into developing more efficient social-aware solutions but also promises a wide range of applications enabled by social and mobile networking, such as routing strategies in Mobile Ad Hoc Networks (MANETs) and worm containment in OSNs. Unfortunately, understanding this structure is very challenging, especially in dynamic social networks where social interactions are evolving rapidly. Our work focuses on the following questions: How can we efficiently identify communities in dynamic social networks? How can we adaptively update the network community structure based on its history instead of recomputing from scratch? To this end, we present Quick Community Adaptation (QCA), an adaptive modularity-based framework for not only discovering but also tracing the evolution of network communities in dynamic OSNs. QCA is very fast and efficient in the sense that it adaptively updates and discovers the new community structure based on its history together with the network changes only. This flexible approach makes QCA an ideal framework applicable for analyzing large-scale dynamic social networks due to its lightweight computing-resource requirement. To illustrate the effectiveness of our framework, we extensively test QCA on both synthesized and real-world social networks including Enron, arXiv e-print citation, and Facebook networks. Finally, we demonstrate the applicability of QCA in real applications: (1) A social-aware message forwarding strategy in MANETs, and (2) worm propagation containment in OSNs. Competitive results in comparison with other methods reveal that social-based techniques employing QCA as a community detection core outperform current available methods.

Publication types

  • Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

  • Algorithms
  • Community Networks*
  • Computer Simulation
  • Humans
  • Internet
  • Models, Statistical
  • Residence Characteristics
  • Social Behavior
  • Social Networking*
  • Social Support
  • Software

Grants and funding

This work is partially supported by NSF CAREER Award #0953284 and DTRA YIP HDTRA1-09-1-0061. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.