Parallel EquiTruss

In many real-world applications, people are more interested in the communities pertaining to an entity (vertex in a graph) rather than the breakdown of the entire graph into different communities. For instance, a user in a social network may be interested in the social groups/communities he/she participates in rather than all the communities in the network. This is helpful in the application fields such as customer grouping, intelligent product advertising, rumor/disease propagation analysis, and criminology. There have been goal-oriented local community discovery models proposed based on graph motifs such as k-core, clique/quasi-clique, and k-truss. The goal of this project is to design a parallel k-truss-based local community detection. Our motivations for choosing k-truss as the core building block of the local community are: 1) Graph motifs discovery based on clique is too restrictive to find in a real-world scenario in addition to the fact that it is not a polynomially tractable problem, 2) The k-core problem is a generalization of the clique. Despite being polynomially solvable, k-core has the disadvantage of being promiscuous, i.e., it lacks cohesion, an important property of the community sub-graph, 3) k-truss, a relaxed form of the clique, can be computed in polynomial time. k-truss uses a higher-order graph motif of triangle connectivity as the building block for the formulation of a community instead of primitive features such as vertex set or edge set thus enabling a comprehensive model of multiple overlapping communities 4) The state-of-the-art k-truss-oriented community search formulations despite seeming promising, cannot utilize modern-day multi-core or many-cores platforms for processing massive networks in a shorter time frame.