TY - GEN
T1 - Persistent community search in temporal networks
AU - Li, Rong Hua
AU - Su, Jiao
AU - Qin, Lu
AU - Yu, Jeffrey Xu
AU - Dai, Qiangqiang
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/10/24
Y1 - 2018/10/24
N2 - Community search is a fundamental graph mining task. Unfortunately, most previous community search studies focus mainly on identifying communities in a network without temporal information. In this paper, we study the problem of finding persistent communities in a temporal network, in which every edge is associated with a timestamp. Our goal is to identify the communities that are persistent over time. To this end, we propose a novel persistent community model called (θ,⊺) community. We prove that the problem of identifying the maximum persistent k-core is NP-hard. To solve this problem, we propose a novel branch and bound algorithm with several carefully-designed pruning rules to find the maximum (θ,⊺)-persistent. We conduct k-cores efficiently. We conduct extensive experiments in several real-world temporal networks. The results demonstrate the efficiency, scalability, and effectiveness of the proposed solutions.
AB - Community search is a fundamental graph mining task. Unfortunately, most previous community search studies focus mainly on identifying communities in a network without temporal information. In this paper, we study the problem of finding persistent communities in a temporal network, in which every edge is associated with a timestamp. Our goal is to identify the communities that are persistent over time. To this end, we propose a novel persistent community model called (θ,⊺) community. We prove that the problem of identifying the maximum persistent k-core is NP-hard. To solve this problem, we propose a novel branch and bound algorithm with several carefully-designed pruning rules to find the maximum (θ,⊺)-persistent. We conduct k-cores efficiently. We conduct extensive experiments in several real-world temporal networks. The results demonstrate the efficiency, scalability, and effectiveness of the proposed solutions.
KW - Community Search
KW - Persistent Community
KW - Temporal network
KW - k-core
UR - http://www.scopus.com/inward/record.url?scp=85057072297&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2018.00077
DO - 10.1109/ICDE.2018.00077
M3 - Conference contribution
AN - SCOPUS:85057072297
T3 - Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
SP - 797
EP - 808
BT - Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 34th IEEE International Conference on Data Engineering, ICDE 2018
Y2 - 16 April 2018 through 19 April 2018
ER -