HUBify: Efficient Estimation of Central Entities Across Multiplex Layer Compositions

Abhishek Santra, Sanjukta Bhowmick, Sharma Chakravarthy

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

3 Scopus citations

Abstract

Graphs or networks are a natural way to analyze inter-related set of entities. When these entities are associated with a diverse number of features, each denoting a specific perspective, then the representation can be simplified by forming a network of layers (one for each feature) or multiplexes. Vertices with high centrality values in the multiplexes represent the most influential vertices. However, detecting central entities in multiplexes for different combinations of features becomes computationally expensive, as the number of layers increases. In this paper, we address the task of efficiently identifying high centrality vertices for any conjunctive (AND) combination of features (as represented by multiplex layers.) We propose efficient heuristics that only use results from individual layers to identify high degree and high closeness centrality vertices. Our approaches, when applied to real-world, multi-featured datasets such as IMDb and traffic accidents, show that we can identify the high centrality vertices with an average accuracy of more than 70-80% while reducing the overall computational time by at least 30%.

Original languageEnglish (US)
Title of host publicationProceeding - 17th IEEE International Conference on Data Mining Workshops, ICDMW 2017
EditorsRaju Gottumukkala, George Karypis, Vijay Raghavan, Xindong Wu, Lucio Miele, Srinivas Aluru, Xia Ning, Guozhu Dong
PublisherIEEE Computer Society
Pages142-149
Number of pages8
ISBN (Electronic)9781538614808
DOIs
StatePublished - Dec 15 2017
Event17th IEEE International Conference on Data Mining Workshops, ICDMW 2017 - New Orleans, United States
Duration: Nov 18 2017Nov 21 2017

Publication series

NameIEEE International Conference on Data Mining Workshops, ICDMW
Volume2017-November
ISSN (Print)2375-9232
ISSN (Electronic)2375-9259

Other

Other17th IEEE International Conference on Data Mining Workshops, ICDMW 2017
CountryUnited States
CityNew Orleans
Period11/18/1711/21/17

Keywords

  • Closeness Centrality
  • Degree Centrality
  • Graph Analysis
  • Lossless Composability
  • Multiplexes

ASJC Scopus subject areas

  • Computer Science Applications
  • Software

Fingerprint Dive into the research topics of 'HUBify: Efficient Estimation of Central Entities Across Multiplex Layer Compositions'. Together they form a unique fingerprint.

  • Cite this

    Santra, A., Bhowmick, S., & Chakravarthy, S. (2017). HUBify: Efficient Estimation of Central Entities Across Multiplex Layer Compositions. In R. Gottumukkala, G. Karypis, V. Raghavan, X. Wu, L. Miele, S. Aluru, X. Ning, & G. Dong (Eds.), Proceeding - 17th IEEE International Conference on Data Mining Workshops, ICDMW 2017 (pp. 142-149). (IEEE International Conference on Data Mining Workshops, ICDMW; Vol. 2017-November). IEEE Computer Society. https://doi.org/10.1109/ICDMW.2017.24