  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
new 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 G, that is, to find the r vertices with
the highest truss-based structural diversity and return their social contexts.
o tackle this problem, we propose an online structural diversity search
algorithm in $O(\rho(m+\mathcal{T}))$ time, where $\rho$, $m$, and
$\mathcal{T}$ are respectively the arboricity, the number of edges, and the
number of triangles in $G$. To improve the efficiency, we design an elegant and
compact index, called TSD-index, for further expediting the search process. 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)$ time.
Extensive experiments demonstrate the effectiveness and efficiency of our
proposed model and algorithms, against state-of-the-art methods.
