TY - GEN
T1 - Local triangle-densest subgraphs
AU - Samusevich, Raman
AU - Danisch, Maximilien
AU - Sozio, Mauro
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/11/21
Y1 - 2016/11/21
N2 - Finding dense subgraphs in large graphs is a key primitive in a variety of real-world application domains, encompassing social network analysis, event detection, problems arising in biology and many others. Several recent works have studied some variants of the classical densest subgraph problem, considering alternative quality measures such as the average number of triangles in the subgraphs and their compactness. Those are desirable properties when the task is to find communities or interesting events in social networks. In our work, we capitalize on previous works and study a variant of the problem where we aim at finding subgraphs which are both compact and contain a large number of triangles. We provide a formal definition for our problem, while developing efficient algorithms with strong theoretical guarantees. Our experimental evaluation on large real-world networks shows the effectiveness of our approach.
AB - Finding dense subgraphs in large graphs is a key primitive in a variety of real-world application domains, encompassing social network analysis, event detection, problems arising in biology and many others. Several recent works have studied some variants of the classical densest subgraph problem, considering alternative quality measures such as the average number of triangles in the subgraphs and their compactness. Those are desirable properties when the task is to find communities or interesting events in social networks. In our work, we capitalize on previous works and study a variant of the problem where we aim at finding subgraphs which are both compact and contain a large number of triangles. We provide a formal definition for our problem, while developing efficient algorithms with strong theoretical guarantees. Our experimental evaluation on large real-world networks shows the effectiveness of our approach.
U2 - 10.1109/ASONAM.2016.7752210
DO - 10.1109/ASONAM.2016.7752210
M3 - Conference contribution
AN - SCOPUS:85006722258
T3 - Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
SP - 33
EP - 40
BT - Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
A2 - Kumar, Ravi
A2 - Caverlee, James
A2 - Tong, Hanghang
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 8th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
Y2 - 18 August 2016 through 21 August 2016
ER -