Parallel algorithms for parameter-free structural diversity search on graphs

Jinbin Huang, Xin Huang*, Yuanyuan Zhu, Jianliang Xu

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


Structural diversity of a user in a social network is the number of social contexts in his/her contact neighborhood. The problem of structural diversity search is to find the top-k vertices with the largest structural diversity in a graph. However, when identifying distinct social contexts, existing structural diversity models (e.g., t-sized component, t-core, and t-brace) are sensitive to an input parameter of t. To address this drawback, we propose a parameter-free structural diversity model. Specifically, we propose a novel notation of discriminativecore, which automatically models various kinds of social contexts without parameter t. Leveraging on discriminativecores and h-index, the structural diversity score for a vertex is calculated. We study the problem of parameter-free structural diversity search in this paper. An efficient top-k search algorithm with a well-designed upper bound for pruning is proposed. To further speed up the computation, we design a novel parallel algorithm for efficient top-k search over large graphs. The parallel algorithm computes diversity scores for a batch of vertices simultaneously using multi-threads. Extensive experiment results demonstrate the parameter sensitivity of existing t-core based model and verify the superiority of our methods.

Original languageEnglish
Pages (from-to)397-417
Number of pages21
JournalWorld Wide Web
Issue number1
Early online date20 Nov 2020
Publication statusPublished - Jan 2021

Scopus Subject Areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

User-Defined Keywords

  • H-index
  • Parallelization
  • Parameter-free
  • Structural diversity search


Dive into the research topics of 'Parallel algorithms for parameter-free structural diversity search on graphs'. Together they form a unique fingerprint.

Cite this