TOPIC: Toward perfect Influence Graph Summarization

Lei Shi, Sibai Sun, Yuan Xuan, Yue Su, Hanghang Tong, Shuai Ma, Yang Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Summarizing large influence graphs is crucial for many graph visualization and mining tasks. Classical graph clustering and compression algorithms focus on summarizing the nodes by their structural-level or attribute-level similarities, but usually are not designed to characterize the flow-level pattern which is the centerpiece of influence graphs. On the other hand, the social influence analysis has been intensively studied, but little is done on the summarization problem without an explicit focus on social networks. Building on the recent study of the Influence Graph Summarization (IGS), this paper presents a new perspective of the underlying flow-based heuristic. It establishes a direct linkage between the optimal summarization and the classic eigenvector centrality of the graph nodes. Such a theoretic linkage has important implications on numerous aspects in the pursuit of a perfect influence graph summarization. In particular, it enables us to develop a suite of algorithms that can: 1) achieve a near-optimal IGS objective, 2) support dynamic summarizations balancing the IGS objective and the stability of transition in navigating the summarization, and 3) scale to million-node graphs with a near-linear computational complexity. Both quantitative experiments on real-world citation networks and the user studies on the task analysis experience demonstrate the effectiveness of the proposed summarization algorithms.

Original languageEnglish (US)
Title of host publication2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1074-1085
Number of pages12
ISBN (Electronic)9781509020195
DOIs
StatePublished - Jun 22 2016
Externally publishedYes
Event32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland
Duration: May 16 2016May 20 2016

Publication series

Name2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016

Other

Other32nd IEEE International Conference on Data Engineering, ICDE 2016
CountryFinland
CityHelsinki
Period5/16/165/20/16

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design
  • Computer Networks and Communications
  • Information Systems
  • Information Systems and Management

Fingerprint Dive into the research topics of 'TOPIC: Toward perfect Influence Graph Summarization'. Together they form a unique fingerprint.

  • Cite this

    Shi, L., Sun, S., Xuan, Y., Su, Y., Tong, H., Ma, S., & Chen, Y. (2016). TOPIC: Toward perfect Influence Graph Summarization. In 2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016 (pp. 1074-1085). [7498314] (2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDE.2016.7498314