Detecting communities in time-evolving proximity networks

Saurav Pandit, Yang Yang, Vikas Kawadia, Sameet Sreenivasan, Nitesh V. Chawla

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The pattern of interactions between individuals in a population contains implicitly within them a remarkable amount of information. This information, if extracted, could be of significant importance in several realms such as containing the spread of disease, understanding information flow in social systems and predicting likely future interactions. A popular method of discovering structure in networks is through community detection which attempts to capture the extent to which that network is different from a random network. However, communities are not very well defined for time-varying networks. In this paper, we introduce the notion of spatio-temporal communities that attempts to capture the structure in spatial connections as well as temporal changes in a network. We illustrate the notion via several examples and list the challenges in effectively discovering spatio-temporal communities. For example, such communities are lost if the temporal interactions are aggregated in a single weighted network since the concurrency information is lost. We present an approach that first extracts concurrency information via node-clustering on each snapshot. Each node is then assigned a vector of community memberships over time, which is then used to group nodes into overlapping communities via recently introduced link clustering techniques. However we measure similarity (of nodes and edges) based on concurrence, i.e. when they existed, if they existed together. We call our approach the co-community algorithm. We validate our approach using several real-world data sets spanning multiple contexts.

Original languageEnglish (US)
Title of host publicationProceedings of the 2011 IEEE 1st International Network Science Workshop, NSW 2011
Pages173-179
Number of pages7
DOIs
StatePublished - 2011
Externally publishedYes
Event2011 IEEE 1st International Network Science Workshop, NSW 2011 - West Point, NY, United States
Duration: Jun 22 2011Jun 24 2011

Publication series

NameProceedings of the 2011 IEEE 1st International Network Science Workshop, NSW 2011

Conference

Conference2011 IEEE 1st International Network Science Workshop, NSW 2011
CountryUnited States
CityWest Point, NY
Period6/22/116/24/11

Keywords

  • community detection
  • contact graph Data mining
  • social network
  • temporal data

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Detecting communities in time-evolving proximity networks'. Together they form a unique fingerprint.

Cite this