Motif-Preserving Dynamic Local Graph Cut

Dawei Zhou, Jingrui He, Hasan Davulcu, Ross MacIejewski

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Modeling and characterizing high-order connectivity patterns are essential for understanding many complex systems, ranging from social networks to collaboration networks, from finance to neuroscience. However, existing works on high-order graph clustering assume that the input networks are static. Consequently, they fail to explore the rich high-order connectivity patterns embedded in the network evolutions, which may play fundamental roles in real applications. For example, in financial fraud detection, detecting loops formed by sequenced transactions helps identify money laundering activities; in emerging trend detection, star-shaped structures showing in a short burst may indicate novel research topics in citation networks. In this paper, we bridge this gap by proposing a local graph clustering framework that captures structure-rich subgraphs, taking into consideration the information of high-order structures in temporal networks. In particular, our motif-preserving dynamic local graph cut framework (MOTLOC) is able to model various user-defined temporal network structures and find clusters with minimum conductance in a polylogarithmic time complexity. Extensive empirical evaluations on synthetic and real networks demonstrate the effectiveness and efficiency of our MOTLOC framework.

Original languageEnglish (US)
Title of host publicationProceedings - 2018 IEEE International Conference on Big Data, Big Data 2018
EditorsYang Song, Bing Liu, Kisung Lee, Naoki Abe, Calton Pu, Mu Qiao, Nesreen Ahmed, Donald Kossmann, Jeffrey Saltz, Jiliang Tang, Jingrui He, Huan Liu, Xiaohua Hu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781538650356
StatePublished - Jan 22 2019
Externally publishedYes
Event2018 IEEE International Conference on Big Data, Big Data 2018 - Seattle, United States
Duration: Dec 10 2018Dec 13 2018

Publication series

NameProceedings - 2018 IEEE International Conference on Big Data, Big Data 2018


Conference2018 IEEE International Conference on Big Data, Big Data 2018
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Computer Science Applications
  • Information Systems


Dive into the research topics of 'Motif-Preserving Dynamic Local Graph Cut'. Together they form a unique fingerprint.

Cite this