Querying Intimate-Core Groups in Weighted Graphs

Dong Zheng, Jianquan Liu, Rong Hua Li, Cigdem Aslay, Yi Cheng Chen, Xin HUANG

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

7 Citations (Scopus)

Abstract

The semantic intimacy of relations in many real-world networks (e.g., social, biological, and communication networks) can be modeled by weighted edges in which the more semantically intimate relations between the nodes translate to smaller edge weights. Recently, the problem of community search that aims to find the cohesive groups containing a given set of query nodes has attracted a great deal of attention. However, the bulk of literature on community search problem assumes a simple unweighted input graph, ignoring how semantically intimate the nodes have in retrieved communities. The discovered communities may have a highly cohesive structure, while they perform poorly in the semantic of intimate connections. In this paper, we investigate a novel problem of Querying Intimate-Core Groups (QICG): Given a weighted undirected graph G, a set of query nodes Q and a positive integer k, to find a connected subgraph of G in which each node has at least k neighbors, and the sum of weights on its edges is minimum among all such subgraphs. We show that the QICG problem is NP-hard. We develop efficient algorithms based on several practical heuristic strategies to enhance the retrieval efficiency. Extensive experiments are conducted on real-world datasets to evaluate efficiency and effectiveness of proposed algorithms. The results confirm that our intimate-core group model outperforms state-of-the-art models in weighted graphs.

Original languageEnglish
Title of host publicationProceedings - IEEE 11th International Conference on Semantic Computing, ICSC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages156-163
Number of pages8
ISBN (Electronic)9781509048960
DOIs
Publication statusPublished - 29 Mar 2017
Event11th IEEE International Conference on Semantic Computing, ICSC 2017 - San Diego, United States
Duration: 30 Jan 20171 Feb 2017

Publication series

NameProceedings - IEEE 11th International Conference on Semantic Computing, ICSC 2017

Conference

Conference11th IEEE International Conference on Semantic Computing, ICSC 2017
Country/TerritoryUnited States
CitySan Diego
Period30/01/171/02/17

Scopus Subject Areas

  • Computer Science Applications
  • Information Systems
  • Computer Networks and Communications

User-Defined Keywords

  • community search
  • Intimate-Core groups
  • k-core
  • weighted graphs

Fingerprint

Dive into the research topics of 'Querying Intimate-Core Groups in Weighted Graphs'. Together they form a unique fingerprint.

Cite this