Rapid Analysis of Network Connectivity
Rapid Analysis of Network Connectivity
复制标题
DOI：
10.1145/3132847.3133170
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Scott Freitas;Hanghang Tong;Nan Cao;Yinglong Xia
中科院分区：
文献类型：
--
作者：
Scott Freitas;Hanghang Tong;Nan Cao;Yinglong Xia
本研究的重点是加速计算时间的两个基础网络算法（k-简单最短路径和最小生成树的一个子集的节点）--各种网络连接挖掘任务背后的基石--的目标是快速找到网络路径和树使用一组用户特定的查询节点。为了促进这一过程，我们利用：（1）多线程算法的变化，（2）网络重用后续查询和（3）一种新的算法，关键相邻顶点（KNV），以减少网络搜索空间。所提出的KNV算法具有双重目的：（a）减少算法分析的计算时间和（B）识别网络中的关键顶点（\textit）。实证结果表明，这种技术的组合显着提高了这两种算法的基线性能。我们还开发了一个网络平台，利用所提出的网络算法，使研究人员和从业人员都可视化和互动与他们的数据集（Pathplane：http://www.path-finder.io。
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 networkpathways andtrees 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 (\textit ). 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.