Truss-Based Structural Diversity Search in Large Graphs

Jinbin Huang, Xin Huang*, Jianliang Xu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Social decisions made by individuals are easily influenced by information from their social neighborhoods. A key predictor of social contagion is the multiplicity of social contexts inside the individual’s contact neighborhood, which is termed structural diversity. However, the existing models have limited decomposability for analyzing large-scale networks, and suffer from the inaccurate reflection of social context diversity. In this paper, we propose a truss-based structural diversity model to overcome the weak decomposability. Based on this model, we study a novel problem of truss-based structural diversity search in a graph GG, that is, to find the rr vertices with the highest truss-based structural diversity and return their social contexts. To tackle this problem, we propose an online structural diversity search algorithm in O(ρ(m+T))O(ρ(m+T)) time, where ρρ, mm, and TT are respectively the arboricity, the number of edges, and the number of triangles in GG. To improve the efficiency, we design an elegant and compact index, called TSD-index, which keeps the structural diversity information for all individual vertices. We further optimize the structure of TSD-index into a highly compressed GCT-index. Our GCT-index-based structural diversity search utilizes the global triangle information for fast index construction and finds answers in O(m)O(m) time. Extensive experiments demonstrate the effectiveness and efficiency of our proposed model and algorithms, against state-of-the-art methods.
Original languageEnglish
Pages (from-to)4037-4051
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume34
Issue number8
Early online date30 Sep 2020
DOIs
Publication statusPublished - 1 Aug 2022

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • social contagion
  • Structural diversity
  • top-k search
  • truss mining

Fingerprint

Dive into the research topics of 'Truss-Based Structural Diversity Search in Large Graphs'. Together they form a unique fingerprint.

Cite this