Finding Heaviest k-Subgraphs and Events in Social Media

Matthaios Letsios; Oana Denisa Balalau; Maximilien Danisch; Emmanuel Orsini; Mauro Sozio

doi:10.1109/ICDMW.2016.0024

Finding Heaviest k-Subgraphs and Events in Social Media

Matthaios Letsios
, Oana Denisa Balalau
, Maximilien Danisch
, Emmanuel Orsini
, Mauro Sozio

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In recent years, social media have become a useful tool to stay in contact with friends, to share thoughts but also to be informed about events. Users can follow news channels, but they can be the ones reporting updates, which distinguishes social media from traditional media. In this paper, we use a graph mining approach for finding events in a graph constructed starting from posts of users. We develop an exact algorithm for solving the heaviest k-subgraph problem which is an NP-hard problem. Our experimental analysis on large real-world graphs shows that our algorithm is able to compute the exact solutions for k up to 15 or more depending on the structure of the graph. We also develop an approximation version of our algorithm scaling to larger k. In comparison, for this setting, the classical heuristic based on weighted core decomposition only leads to sub-optimal solutions. Finally, we show that our algorithm can be used to find relevant events in Twitter. Indeed, as an event is usually described by a small number of words, our algorithm is a useful tool to detect them.

Original language	English
Title of host publication	Proceedings - 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016
Editors	Carlotta Domeniconi, Francesco Gullo, Francesco Bonchi, Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Ricardo Baeza-Yates, Ricardo Baeza-Yates, Zhi-Hua Zhou, Xindong Wu
Publisher	IEEE Computer Society
Pages	113-120
Number of pages	8
ISBN (Electronic)	9781509054725
DOIs	https://doi.org/10.1109/ICDMW.2016.0024
Publication status	Published - 2 Jul 2016
Externally published	Yes
Event	16th IEEE International Conference on Data Mining Workshops, ICDMW 2016 - Barcelona, Spain Duration: 12 Dec 2016 → 15 Dec 2016

Publication series

Name	IEEE International Conference on Data Mining Workshops, ICDMW
Volume	0
ISSN (Print)	2375-9232
ISSN (Electronic)	2375-9259

Conference

Conference	16th IEEE International Conference on Data Mining Workshops, ICDMW 2016
Country/Territory	Spain
City	Barcelona
Period	12/12/16 → 15/12/16

Keywords

Branch and bound
Densest k-subgraph
Event detection
Heaviest k-subgraph

Access to Document

10.1109/ICDMW.2016.0024

Cite this

Letsios, M., Balalau, O. D., Danisch, M., Orsini, E., & Sozio, M. (2016). Finding Heaviest k-Subgraphs and Events in Social Media. In C. Domeniconi, F. Gullo, F. Bonchi, F. Bonchi, J. Domingo-Ferrer, R. Baeza-Yates, R. Baeza-Yates, R. Baeza-Yates, Z.-H. Zhou, & X. Wu (Eds.), Proceedings - 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016 (pp. 113-120). Article 7836655 (IEEE International Conference on Data Mining Workshops, ICDMW; Vol. 0). IEEE Computer Society. https://doi.org/10.1109/ICDMW.2016.0024

Letsios, Matthaios ; Balalau, Oana Denisa ; Danisch, Maximilien et al. / Finding Heaviest k-Subgraphs and Events in Social Media. Proceedings - 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016. editor / Carlotta Domeniconi ; Francesco Gullo ; Francesco Bonchi ; Francesco Bonchi ; Josep Domingo-Ferrer ; Ricardo Baeza-Yates ; Ricardo Baeza-Yates ; Ricardo Baeza-Yates ; Zhi-Hua Zhou ; Xindong Wu. IEEE Computer Society, 2016. pp. 113-120 (IEEE International Conference on Data Mining Workshops, ICDMW).

@inproceedings{6fc8a98150d34570a4aa07512340a3dc,

title = "Finding Heaviest k-Subgraphs and Events in Social Media",

abstract = "In recent years, social media have become a useful tool to stay in contact with friends, to share thoughts but also to be informed about events. Users can follow news channels, but they can be the ones reporting updates, which distinguishes social media from traditional media. In this paper, we use a graph mining approach for finding events in a graph constructed starting from posts of users. We develop an exact algorithm for solving the heaviest k-subgraph problem which is an NP-hard problem. Our experimental analysis on large real-world graphs shows that our algorithm is able to compute the exact solutions for k up to 15 or more depending on the structure of the graph. We also develop an approximation version of our algorithm scaling to larger k. In comparison, for this setting, the classical heuristic based on weighted core decomposition only leads to sub-optimal solutions. Finally, we show that our algorithm can be used to find relevant events in Twitter. Indeed, as an event is usually described by a small number of words, our algorithm is a useful tool to detect them.",

keywords = "Branch and bound, Densest k-subgraph, Event detection, Heaviest k-subgraph",

author = "Matthaios Letsios and Balalau, \{Oana Denisa\} and Maximilien Danisch and Emmanuel Orsini and Mauro Sozio",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016 ; Conference date: 12-12-2016 Through 15-12-2016",

year = "2016",

month = jul,

day = "2",

doi = "10.1109/ICDMW.2016.0024",

language = "English",

series = "IEEE International Conference on Data Mining Workshops, ICDMW",

publisher = "IEEE Computer Society",

pages = "113--120",

editor = "Carlotta Domeniconi and Francesco Gullo and Francesco Bonchi and Francesco Bonchi and Josep Domingo-Ferrer and Ricardo Baeza-Yates and Ricardo Baeza-Yates and Ricardo Baeza-Yates and Zhi-Hua Zhou and Xindong Wu",

booktitle = "Proceedings - 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016",

}

Letsios, M, Balalau, OD, Danisch, M, Orsini, E & Sozio, M 2016, Finding Heaviest k-Subgraphs and Events in Social Media. in C Domeniconi, F Gullo, F Bonchi, F Bonchi, J Domingo-Ferrer, R Baeza-Yates, R Baeza-Yates, R Baeza-Yates, Z-H Zhou & X Wu (eds), Proceedings - 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016., 7836655, IEEE International Conference on Data Mining Workshops, ICDMW, vol. 0, IEEE Computer Society, pp. 113-120, 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016, Barcelona, Spain, 12/12/16. https://doi.org/10.1109/ICDMW.2016.0024

Finding Heaviest k-Subgraphs and Events in Social Media. / Letsios, Matthaios; Balalau, Oana Denisa; Danisch, Maximilien et al.
Proceedings - 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016. ed. / Carlotta Domeniconi; Francesco Gullo; Francesco Bonchi; Francesco Bonchi; Josep Domingo-Ferrer; Ricardo Baeza-Yates; Ricardo Baeza-Yates; Ricardo Baeza-Yates; Zhi-Hua Zhou; Xindong Wu. IEEE Computer Society, 2016. p. 113-120 7836655 (IEEE International Conference on Data Mining Workshops, ICDMW; Vol. 0).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Finding Heaviest k-Subgraphs and Events in Social Media

AU - Letsios, Matthaios

AU - Balalau, Oana Denisa

AU - Danisch, Maximilien

AU - Orsini, Emmanuel

AU - Sozio, Mauro

PY - 2016/7/2

Y1 - 2016/7/2

N2 - In recent years, social media have become a useful tool to stay in contact with friends, to share thoughts but also to be informed about events. Users can follow news channels, but they can be the ones reporting updates, which distinguishes social media from traditional media. In this paper, we use a graph mining approach for finding events in a graph constructed starting from posts of users. We develop an exact algorithm for solving the heaviest k-subgraph problem which is an NP-hard problem. Our experimental analysis on large real-world graphs shows that our algorithm is able to compute the exact solutions for k up to 15 or more depending on the structure of the graph. We also develop an approximation version of our algorithm scaling to larger k. In comparison, for this setting, the classical heuristic based on weighted core decomposition only leads to sub-optimal solutions. Finally, we show that our algorithm can be used to find relevant events in Twitter. Indeed, as an event is usually described by a small number of words, our algorithm is a useful tool to detect them.

AB - In recent years, social media have become a useful tool to stay in contact with friends, to share thoughts but also to be informed about events. Users can follow news channels, but they can be the ones reporting updates, which distinguishes social media from traditional media. In this paper, we use a graph mining approach for finding events in a graph constructed starting from posts of users. We develop an exact algorithm for solving the heaviest k-subgraph problem which is an NP-hard problem. Our experimental analysis on large real-world graphs shows that our algorithm is able to compute the exact solutions for k up to 15 or more depending on the structure of the graph. We also develop an approximation version of our algorithm scaling to larger k. In comparison, for this setting, the classical heuristic based on weighted core decomposition only leads to sub-optimal solutions. Finally, we show that our algorithm can be used to find relevant events in Twitter. Indeed, as an event is usually described by a small number of words, our algorithm is a useful tool to detect them.

KW - Branch and bound

KW - Densest k-subgraph

KW - Event detection

KW - Heaviest k-subgraph

U2 - 10.1109/ICDMW.2016.0024

DO - 10.1109/ICDMW.2016.0024

M3 - Conference contribution

AN - SCOPUS:85015225732

T3 - IEEE International Conference on Data Mining Workshops, ICDMW

SP - 113

EP - 120

BT - Proceedings - 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016

A2 - Domeniconi, Carlotta

A2 - Gullo, Francesco

A2 - Bonchi, Francesco

A2 - Domingo-Ferrer, Josep

A2 - Baeza-Yates, Ricardo

A2 - Zhou, Zhi-Hua

A2 - Wu, Xindong

PB - IEEE Computer Society

T2 - 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016

Y2 - 12 December 2016 through 15 December 2016

ER -

Letsios M, Balalau OD, Danisch M, Orsini E, Sozio M. Finding Heaviest k-Subgraphs and Events in Social Media. In Domeniconi C, Gullo F, Bonchi F, Bonchi F, Domingo-Ferrer J, Baeza-Yates R, Baeza-Yates R, Baeza-Yates R, Zhou ZH, Wu X, editors, Proceedings - 16th IEEE International Conference on Data Mining Workshops, ICDMW 2016. IEEE Computer Society. 2016. p. 113-120. 7836655. (IEEE International Conference on Data Mining Workshops, ICDMW). doi: 10.1109/ICDMW.2016.0024

Finding Heaviest k-Subgraphs and Events in Social Media

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this