Finding Heaviest k-Subgraphs and Events in Social Media

摘要

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.