X-Rank: Explainable Ranking in Complex Multi-Layered Networks

Jian Kang*, Scott Freitas*, Haichao Yu, Yinglong Xia, Hanghang Tong

This research is an effort to develop visual-graphic interfaces for sense-making of large networks. The goal is to create an algorithmic model and prototype that will allow researchers to study and analyze the hidden patterns in a wide range of networks by identifying local communities around a given seed node using the network topology and attribute information of the graph.

Abstract

Local graph partitioning is a key graph mining tool that allows researchers to identify small groups of interrelated nodes (e.g., people) and their connective edges (e.g., interactions). As local graph partitioning focuses primarily on the graph structure (vertices and edges), it often fails to consider the additional information contained in the attributes. We propose a scalable algorithm to improve local graph partitioning by taking into account both the graph structure and attributes. Experimental results show that our proposed AttriPart algorithm finds up to 1.6x denser local partitions, while running approximately 43x faster than traditional local partitioning techniques (PageRank-Nibble).

Citation

X-Rank: Explainable Ranking in Complex Multi-Layered Networks
Jian Kang*, Scott Freitas*, Haichao Yu, Yinglong Xia, Hanghang Tong
ACM International Conference on Information and Knowledge Management (CIKM). Turin, Italy, 2018.
Project PDF BibTeX * Authors contributed equally