PROJECT TITLE :

Truss-based Structural Diversity Search in Graphs

ABSTRACT:

Individuals' social decisions are easily swayed by the information that circulates within the social communities in which they live. Structural diversity, also known as the number of different social contexts that exist within an individual's contact neighborhood, is an important indicator of the likelihood of social contagion occurring. However, the currently available models suffer from inaccuracies in their reflection of the variety of social contexts and have restricted decomposability for the analysis of large-scale networks. As a solution to the problem of weak decomposability, the authors of this paper suggest a structural diversity model that is truss-based. On the basis of this model, we investigate a new problem called truss-based structural diversity search in a graph G. The goal of this problem is to locate the r vertices that have the highest truss-based structural diversity and then return their respective social contexts. In order to address this issue, we have developed an online algorithm for searching for structural diversity that runs in O((m+T)) time, where, m, and T refer, respectively, to the arboricity of G, the number of edges in G, and the number of triangles in G. In order to make the process more effective, we devised a sophisticated and condensed index that we called the TSD-index. This index stores information regarding the structural diversity of each individual vertex. We perform additional optimization on the structure of the TSD-index to produce a GCT-index that is extremely compressed. Our GCT-index-based structural diversity search makes use of the information about global triangles for the purpose of quickly constructing indices, and it discovers answers in O(m) time. Extensive testing has shown that our proposed model and algorithms are superior to other, more contemporary approaches, both in terms of their effectiveness and their efficiency.