Parallel algorithms for parameter-free structural diversity search on graphs
- PDF / 1,540,765 Bytes
- 21 Pages / 439.642 x 666.49 pts Page_size
- 28 Downloads / 187 Views
Parallel algorithms for parameter-free structural diversity search on graphs Jinbin Huang1 · Xin Huang1 · Yuanyuan Zhu2 · Jianliang Xu1 Received: 21 March 2020 / Revised: 22 July 2020 / Accepted: 21 September 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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 discriminative core, which automatically models various kinds of social contexts without parameter t. Leveraging on discriminative cores 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. Keywords Structural diversity search · Parallelization · Parameter-free · H-index
This article belongs to the Topical Collection: Special Issue on Web Information Systems Engineering 2019 Guest Editors: Reynold Cheng, Nikos Mamoulis, and Xin Huang Xin Huang
[email protected] Jinbin Huang [email protected] Yuanyuan Zhu [email protected] Jianliang Xu [email protected] 1
Hong Kong Baptist University, Kowloon Tong, Hong Kong
2
Wuhan University, Wuhan, China
World Wide Web
1 Introduction Nowadays, information spreads quickly and widely on social networks (e.g., Twitter, Facebook) [24, 29, 35, 47]. Individuals are usually influenced easily by the information received from their social neighborhoods. Recent studies show that social decisions made by individuals often depend on the multiplicity of social contexts inside his/her contact neighborhood, which is termed as structural diversity [22, 47]. Individuals with larger structural diversity, are shown to have higher probability to be affected in the process of social contagion [47]. Structural diversity search, finding the individuals with the highest structural diversity in graphs, has many applications such as political campaigns [26], viral marketing [30], promotion of health practices [47], facebook user invitations [47], twitter user retention [45], social reputation evaluation [53] and so on. In the literature, several structural diversity models (e.g., t-sized component, t
Data Loading...
