Finding dynamic dense subgraphs

Polina Rozenshtein, Nikolaj Tatti, Aristides Gionis

Research output: Contribution to journalArticleScientificpeer-review

12 Citations (Scopus)


Online social networks are often defined by considering interactions of entities at an aggregate level. For example, a call graph is formed among individuals who have called each other at least once; or at least κ times. Similarly, in social-media platforms, we consider implicit social networks among users who have interacted in some way, e.g., have made a conversation, have commented to the content of each other, and so on. Such definitions have been used widely in the literature and they have offered significant insights regarding the structure of social networks. However, it is obvious that they suffer from a severe limitation: They neglect the precise time that interactions among the network entities occur. In this article, we consider interaction networks, where the data description contains not only information about the underlying topology of the social network, but also the exact time instances that network entities interact. In an interaction network, an edge is associated with a timestamp, and multiple edges may occur for the same pair of entities. Consequently, interaction networks offer a more fine-grained representation, which can be leveraged to reveal otherwise hidden dynamic phenomena. In the setting of interaction networks, we study the problem of discovering dynamic dense subgraphs whose edges occur in short time intervals. We view such subgraphs as fingerprints of dynamic activity occurring within network communities. Such communities represent groups of individuals who interact with each other in specific time instances, for example, a group of employees who work on a project and whose interaction intensifies before certain project milestones. We prove that the problem we define is NPhard, and we provide efficient algorithms by adapting techniques for finding dense subgraphs. We also show how to speed-up the proposed methods by exploiting concavity properties of our objective function and by the means of fractional programming. We perform extensive evaluation of the proposed methods on synthetic and real datasets, which demonstrates the validity of our approach and shows that our algorithms can be used to obtain high-quality results.

Original languageEnglish
Article number27
Pages (from-to)1-30
JournalACM Transactions on Knowledge Discovery from Data
Issue number3
Publication statusPublished - 1 Mar 2017
MoE publication typeA1 Journal article-refereed


  • Community Discovery
  • Dense Subgraphs
  • Dynamic Graphs
  • Graph Mining
  • Interaction Networks
  • Social-Network Analysis
  • Time-Evolving Networks

Fingerprint Dive into the research topics of 'Finding dynamic dense subgraphs'. Together they form a unique fingerprint.

Cite this