TY - JOUR
T1 - Truss-Based Structural Diversity Search in Large Graphs
AU - Huang, Jinbin
AU - Huang, Xin
AU - Xu, Jianliang
N1 - Funding Information:
This work was partially supported by NSFC 61702435, RGC 12200917, 12201018, CRF C6030-18GF, and Guangdong Science and Technology Special Fund SDZX2019042.
Publisher copyright:
© 2020 IEEE.
PY - 2022/8/1
Y1 - 2022/8/1
N2 - 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.
AB - 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.
KW - social contagion
KW - Structural diversity
KW - top-k search
KW - truss mining
UR - http://www.scopus.com/inward/record.url?scp=85134191461&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2020.3027950
DO - 10.1109/TKDE.2020.3027950
M3 - Journal article
AN - SCOPUS:85134191461
SN - 1041-4347
VL - 34
SP - 4037
EP - 4051
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 8
ER -