skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

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

Liu, Guanfeng ; Liu, Yi ; Zheng, Kai ; Liu, An ; Li, Zhixu ; Wang, Yang ; Zhou, Xiaofang

IEEE transactions on knowledge and data engineering, 2018-06, Vol.30 (6), p.1050-1064 [Periódico revisado por pares]

New York: IEEE

Texto completo disponível

Citações Citado por
  • Título:
    MCS-GPM: Multi-Constrained Simulation Based Graph Pattern Matching in Contextual Social Graphs
  • Autor: Liu, Guanfeng ; Liu, Yi ; Zheng, Kai ; Liu, An ; Li, Zhixu ; Wang, Yang ; Zhou, Xiaofang
  • Assuntos: Algorithms ; Computational modeling ; Computer simulation ; Context modeling ; Data models ; Decompressing ; Empirical analysis ; Graph matching ; Graph pattern matching ; Graph theory ; Graphs ; Heuristic methods ; Indexes ; Medical science ; Network analysis ; Pattern matching ; Simulation ; social graph ; Social network services ; Social networks ; Time complexity
  • É parte de: IEEE transactions on knowledge and data engineering, 2018-06, Vol.30 (6), p.1050-1064
  • Descrição: Graph Pattern Matching (GPM) has been used in lots of areas, like biology, medical science, and physics. With the advent of Online Social Networks (OSNs), recently, GPM has been playing a significant role in social network analysis, which has been widely used in, for example, finding experts, social community mining, and social position detection. Given a query which contains a pattern graph G Q and a data graph G D , a GPM algorithm finds those subgraphs, G M , that match G Q in G D . However, the existing GPM methods do not consider the multiple end-to-end constraints of the social contexts, like social relationships, social trust, and social positions on edges in G Q , which are commonly found in various applications, such as crowdsourcing travel, social network based ecommerce, and study group selection, etc. In this paper, we first conceptually extend Bounded Simulation to Multi-Constrained Simulation (MCS), and propose a novel NP-Complete Multi-Constrained Graph Pattern Matching (MC-GPM) problem. Then, to address the efficiency issue in large-scale MC-GPM, we propose a new concept called Strong Social Component (SSC), consisting of participants with strong social connections. We also propose an approach to identifying SSCs, and propose a novel index method and a graph compression method for SSC. Moreover, we devise a multithreading heuristic algorithm, called M-HAMC, to bidirectionally search the MC-GPM results in parallel without decompressing graphs. An extensive empirical study over five real-world large-scale social graphs has demonstrated the effectiveness and efficiency of our approach.
  • Editor: New York: IEEE
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.