TY - GEN
T1 - Detecting statistically significant events in large heterogeneous attribute graphs via densest subgraphs
AU - Li, Yuan
AU - Fan, Xiaolin
AU - Sun, Jing
AU - Zhao, Yuhai
AU - Wang, Guoren
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2020.
PY - 2020
Y1 - 2020
N2 - With the widespread of social platforms, event detection is becoming an important problem in social media. Yet, the large amount of content accumulated on social platforms brings great challenges. Moreover, the content usually is informal, lacks of semantics and rapidly spreads in dynamic networks, which makes the situation even worse. Existing approaches, including content-based detection and network structure-based detection, only use limited and single information of social platforms that limits the accuracy and integrity of event detection. In this paper, (1) we propose to model the entire social platform as a heterogeneous attribute graph (HAG), including types, entities, relations and their attributes; (2) we exploit non-parametric scan statistics to measure the statistical significance of subgraphs in HAG by considering historical information; (3) we transform the event detection in HAG into a densest subgraph discovery problem in statistical weighted network. Due to its NP-hardness, we propose an efficient approximate method to find the densest subgraphs based on (k, Ψ)-core, and simultaneously the statistical significance is guaranteed. In experiments, we conduct comprehensive empirical evaluations on Weibo data to demonstrate the effectiveness and efficiency of our proposed approaches.
AB - With the widespread of social platforms, event detection is becoming an important problem in social media. Yet, the large amount of content accumulated on social platforms brings great challenges. Moreover, the content usually is informal, lacks of semantics and rapidly spreads in dynamic networks, which makes the situation even worse. Existing approaches, including content-based detection and network structure-based detection, only use limited and single information of social platforms that limits the accuracy and integrity of event detection. In this paper, (1) we propose to model the entire social platform as a heterogeneous attribute graph (HAG), including types, entities, relations and their attributes; (2) we exploit non-parametric scan statistics to measure the statistical significance of subgraphs in HAG by considering historical information; (3) we transform the event detection in HAG into a densest subgraph discovery problem in statistical weighted network. Due to its NP-hardness, we propose an efficient approximate method to find the densest subgraphs based on (k, Ψ)-core, and simultaneously the statistical significance is guaranteed. In experiments, we conduct comprehensive empirical evaluations on Weibo data to demonstrate the effectiveness and efficiency of our proposed approaches.
KW - Densest subgraphs
KW - Event detection
KW - Heterogeneous attribute graphs
KW - Statistical significance
UR - http://www.scopus.com/inward/record.url?scp=85090096516&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-55130-8_10
DO - 10.1007/978-3-030-55130-8_10
M3 - Conference contribution
AN - SCOPUS:85090096516
SN - 9783030551292
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 107
EP - 120
BT - Knowledge Science, Engineering and Management - 13th International Conference, KSEM 2020, Proceedings, Part 1
A2 - Li, Gang
A2 - Shen, Heng Tao
A2 - Yuan, Ye
A2 - Wang, Xiaoyang
A2 - Liu, Huawen
A2 - Zhao, Xiang
PB - Springer
T2 - 13th International Conference on Knowledge Science, Engineering and Management, KSEM 2020
Y2 - 28 August 2020 through 30 August 2020
ER -