Rapid analysis of network connectivity

Scott Freitas, Hanghang Tong, Nan Cao, Yinglong Xia

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

3 Scopus citations


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 (PathFinder: http://www.path-finder.io).

Original languageEnglish (US)
Title of host publicationCIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery
Number of pages4
ISBN (Electronic)9781450349185
StatePublished - Nov 6 2017
Event26th ACM International Conference on Information and Knowledge Management, CIKM 2017 - Singapore, Singapore
Duration: Nov 6 2017Nov 10 2017

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings
VolumePart F131841


Other26th ACM International Conference on Information and Knowledge Management, CIKM 2017


  • K-simple shortest paths
  • MST
  • Multi-threading
  • Network visualization
  • Parallel processing
  • Search space reduction
  • Seed nodes

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Business, Management and Accounting(all)


Dive into the research topics of 'Rapid analysis of network connectivity'. Together they form a unique fingerprint.

Cite this