Scalable information flow mining in networks

Karthik Subbian, Chidananda Sridhar, Charu C. Aggarwal, Jaideep Srivastava

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

1 Scopus citations

Abstract

The problem of understanding user activities and their patterns of communication is extremely important in social and collaboration networks. This can be achieved by tracking the dominant content flow trends and their interactions between users in the network. Our approach tracks all possible paths of information flow using its network structure, content propagated and the time of propagation. We also show that the complexity class of this problem is #P-complete. Because most social networks have many activities and interactions, it is inevitable the proposed method will be computationally intensive. Therefore, we propose an efficient method for mining information flow patterns, especially in large networks, using distributed vertex-centric computational models. We use the Gather-Apply-Scatter (GAS) paradigm to implement our approach. We experimentally show that our approach achieves over three orders of magnitude advantage over the state-of-the-art, with an increasing advantage with a greater number of cores. We also study the effectiveness of the discovered content flow patterns by using it in the context of an influence analysis application.

Original languageEnglish (US)
Title of host publicationMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2014, Proceedings
PublisherSpringer- Verlag
Pages130-146
Number of pages17
EditionPART 3
ISBN (Print)9783662448441
DOIs
StatePublished - Jan 1 2014
EventEuropean Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2014 - Nancy, France
Duration: Sep 15 2014Sep 19 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 3
Volume8726 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherEuropean Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2014
CountryFrance
CityNancy
Period9/15/149/19/14

    Fingerprint

Keywords

  • Influence Analysis Network-centric approach
  • Information Flow Mining
  • Scalable Influence Analysis
  • Vertex-centric models

Cite this

Subbian, K., Sridhar, C., Aggarwal, C. C., & Srivastava, J. (2014). Scalable information flow mining in networks. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2014, Proceedings (PART 3 ed., pp. 130-146). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8726 LNAI, No. PART 3). Springer- Verlag. https://doi.org/10.1007/978-3-662-44845-8_9