PROJECT TITLE :

MCS-GPM: Multi-Constrained Simulation Based Graph Pattern Matching in Contextual Social Graphs - 2018

ABSTRACT:

Graph Pattern Matching (GPM) has been employed in heaps of areas, like biology, medical science, and physics. With the appearance of On-line Social Networks (OSNs), recently, GPM has been enjoying a vital role in Social Network Analysis, which has been widely used in, as an example, finding experts, social community mining, and social position detection. Given a query that contains a pattern graph G Q and a knowledge graph G D , a GPM algorithm finds those subgraphs, G M , that match G Q in G D . But, the existing GPM ways don't take into account the multiple end-to-finish constraints of the social contexts, like social relationships, social trust, and social positions on edges in G Q , that are commonly found in numerous applications, like crowdsourcing travel, social network based ecommerce, and study group choice, etc. In this Project, we tend to initial conceptually extend Bounded Simulation to Multi-Constrained Simulation (MCS), and propose a unique NP-Complete Multi-Constrained Graph Pattern Matching (MC-GPM) problem. Then, to deal with the potency issue in giant-scale MC-GPM, we have a tendency to propose a new concept known as Sturdy Social Element (SSC), consisting of participants with sturdy social connections. We have a tendency to conjointly propose an approach to identifying SSCs, and propose a novel index method and a graph compression technique for SSC. Moreover, we devise a multithreading heuristic algorithm, referred to as M-HAMC, to bidirectionally search the MC-GPM results in parallel without decompressing graphs. An intensive empirical study over five real-world giant-scale social graphs has demonstrated the effectiveness and potency of our approach.