Volume 126, Number 4, May 2019
|Number of page(s)||6|
|Section||Interdisciplinary Physics and Related Areas of Science and Technology|
|Published online||24 June 2019|
Community detection in temporal networks via a spreading process
1 School of Computer Science and Engineering, Northwestern Polytechnical University - Xi'an, China
2 Center for OPTical IMagery Analysis and Learning (OPTIMAL), Northwestern Polytechnical University Xi'an, China
3 School of Mechanical Engineering, Northwestern Polytechnical University - Xi'an, China
4 College of Information and Computer Science, Southwest University - Chongqing, China
5 World Research Hub Initiative, Institute of Innovative Research, Tokyo Institute of Technology - Tokyo, Japan
Received: 12 April 2019
Accepted: 14 May 2019
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.
PACS: 89.75.-k – Complex systems / 89.75.Fb – Structures and organization in complex systems / 02.50.-r – Probability theory, stochastic processes, and statistics
© EPLA, 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.