Community detection in temporal networks via a spreading process

¹ School of Computer Science and Engineering, Northwestern Polytechnical University - Xi'an, China
² Center for OPTical IMagery Analysis and Learning (OPTIMAL), Northwestern Polytechnical University Xi'an, China
³ School of Mechanical Engineering, Northwestern Polytechnical University - Xi'an, China
⁴ College of Information and Computer Science, Southwest University - Chongqing, China
⁵ World Research Hub Initiative, Institute of Innovative Research, Tokyo Institute of Technology - Tokyo, Japan

^(b) li@nwpu.edu.cn
^(c) mjusup@gmail.com
^(d) zhenwang0@gmail.com

Received: 12 April 2019
Accepted: 14 May 2019

Abstract

Time-evolving relationships between entities in many complex systems are captured by temporal networks, wherein detecting the network components, i.e., communities or subgraphs, is an important task. A vast majority of existing algorithms, however, treats temporal networks as a collection of snapshots, thus struggling with stability and continuity of detected communities. Inspired by an observation that similarly behaving agents tend to self-organise into the same cluster during epidemic spreading, we devised a novel community detection approach for temporal networks based on a susceptible-infectious-recovered-like (SIR-like) spreading process. Specifically, we used a Markov model of the spreading process to characterise each network node with a probability of getting infected, and subsequently recovering, when the infection starts from every other node in the network. This led to a similarity measure whereby nodes that easily infect one another are considered closer together. To account for network time evolution, we used communities from the preceding time step to modulate spreading in the current time step. Extensive simulations show that our technique outperforms several state-of-the-art methods in synthetic and real-world temporal networks alike.