Rapid Analysis of Network Connectivity

Scott Freitas, Hanghang Tong, Nan Cao, Yinglong Xia

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 and characterizing connectivity between a set of pre-marked nodes within large networks.

Abstract

This research focuses on accelerating the computational time of two base network algorithms (k-simple shortest paths and minimum spanning tree for a subset of nodes)–cornerstones behind a variety of network connectivity mining tasks–with the goal of rapidly finding network pathways and trees using a set of user-specific query nodes. To facilitate this process we utilize: (1) multi-threaded algorithm variations, (2) network re-use for subsequent queries and (3) a novel algorithm, Key Neighboring Vertices (KNV), to reduce the network search space. The proposed KNV algorithm serves a dual purpose: (a) to reduce the computation time for algorithmic analysis and (b) to identify key vertices in the network (context). Empirical results indicate this combination of techniques significantly improves the baseline performance of both algorithms. We have also developed a web platform utilizing the proposed network algorithms to enable researchers and practitioners to both visualize and interact with their datasets.

Citation

Rapid Analysis of Network Connectivity
Scott Freitas, Hanghang Tong, Nan Cao, Yinglong Xia
ACM International Conference on Information and Knowledge Management (CIKM). Singapore, 2017.
Project PDF Video Code BibTeX Best Demo Paper, Runner up