• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Capture and Reconstruction of the Topology of Undirected Graphs from Partial Coordinates: A Matrix Completion Based Approach.
【24h】

Capture and Reconstruction of the Topology of Undirected Graphs from Partial Coordinates: A Matrix Completion Based Approach.

机译：从局部坐标捕获和重构无向图的拓扑：一种基于矩阵完成的方法。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

With the advancement in science and technology, new types of complex networks have become common place across varied domains such as computer networks, Internet, bio-technological studies, sociology, and condensed matter physics. The surge of interest in research towards graphs and topology can be attributed to important applications such as graph representation of words in computational linguistics, identification of terrorists for national security, studying complicated atomic structures, and modeling connectivity in condensed matter physics. Well-known social networks, Facebook, and twitter, have millions of users, while the science citation index is a repository of millions of records and citations. These examples indicate the importance of efficient techniques for measuring, characterizing and mining large and complex networks.;Often analysis of graph attributes to understand the graph topology and embedded properties on these complex graphs becomes difficult due to causes such need to process huge data volumes, lack of compressed representation forms and lack of complete information. Due to improper or inadequate acquiring processes, inaccessibility, etc., often we end up with partial graph representational data. Thus there is immense significance in being able to extract this missing information from the available data. Therefore obtaining the topology of a graph, such as a communication network or a social network from incomplete information is our research focus. Specifically, this research addresses the problem of capturing and reconstructing the topology of a network from a small set of path length measurements. An accurate solution for this problem also provides means of describing graphs with a compressed representation.;A technique to obtain the topology from only a partial set of information about network paths is presented. Specifically, we demonstrate the capture of the network topology from a small set of measurements corresponding to a) shortest hop distances of nodes with respect to small set of nodes called as anchors, or b) a set of pairwise hop distances between random node pairs. These two measurement sets can be related to the Distance matrix D, a common representation of the topology, where an entry contains the shortest hop distance between two nodes. In an anchor based method, the shortest hop distances of nodes to a set of M anchors constitute what is known as a Virtual Coordinate (VC) matrix. This is a submatrix of columns of D corresponding to the anchor nodes. Random pairwise measurements correspond to a random subset of elements of D. The proposed technique depends on a low rank matrix completion method based on extended Robust Principal Component Analysis to extract the unknown elements. The application of the principles of matrix completion relies on the conjecture that many natural data sets are inherently low dimensional and thus corresponding matrix is relatively low ranked. We demonstrate that this is applicable to D of many large-scale networks as well. Thus we are able to use results from the theory of matrix completion for capturing the topology.;Two important types of graphs have been used for evaluation of the proposed technique, namely, Wireless Sensor Network (WSN) graphs and social network graphs. For WSN examples, we use the Topology Preserving Map (TPM), which is a homeomorphic representation of the original layout, to evaluate the effectiveness of the technique from partial sets of entries of VC matrix. A double centering based approach is used to evaluate the TPMs from VCs, in comparison with the existing non-centered approach. Results are presented for both random anchors and nodes that are farthest apart on the boundaries. The idea of obtaining topology is extended towards social network link prediction. The significance of this result lies in the fact that with increasing privacy concerns, obtaining the data in the form of VC matrix or as hop distance matrix becomes difficult. This approach of predicting the unknown entries of a matrix provides a novel approach for social network link predictions, and is supported by the fact that the distance matrices of most real world networks are naturally low ranked.;The accuracy of the proposed techniques is evaluated using 4 different WSN and 3 different social networks. Two 2D and two 3D networks have been used for WSNs with the number of nodes ranging from 500 to 1600. We are able to obtain accurate TPMs for both random anchors and extreme anchors with only 20% to 40% of VC matrix entries. The mean error quantifies the error introduced in TPMs due to unknown entries. The results indicate that even with 80% of entries missing, the mean error is around 35% to 45%.;The Facebook, Collaboration and Enron Email sub networks, with 744, 4158, 3892 nodes respectively, have been used for social network capture. The results obtained are very promising. With 80% of information missing in the hop-distance matrix, a maximum error of only around 6% is incurred. The error in prediction of hop distance is less than 0.5 hops. This has also opened up the idea of compressed representation of networks by its VC matrix.
机译：随着科学技术的进步，新型的复杂网络已经在计算机网络，Internet，生物技术研究，社会学和凝聚态物理等各个领域中变得司空见惯。对图形和拓扑的研究兴趣之所以激增，可以归因于重要的应用，例如计算语言学中的单词图形表示，为国家安全确定恐怖分子，研究复杂的原子结构以及在凝聚态物理中建模连通性。著名的社交网络，Facebook和Twitter，拥有数百万用户，而科学引文索引是数百万条记录和引文的存储库。这些示例说明了测量，表征和挖掘大型和复杂网络的有效技术的重要性。由于由于需要处理大量数据，通常难以分析图属性以了解图拓扑和这些复杂图上的嵌入属性，缺少压缩的表示形式和完整的信息。由于不正确或不适当的获取过程，不可访问性等，通常我们最终会得到部分图形表示数据。因此，能够从可用数据中提取这种丢失的信息具有极其重要的意义。因此，从不完整的信息中获取图的拓扑结构（例如通信网络或社交网络）是我们的研究重点。具体而言，这项研究解决了从一小套路径长度测量中捕获和重建网络拓扑的问题。针对此问题的准确解决方案还提供了以压缩表示形式描述图的方法。提出了一种仅从有关网络路径的部分信息中获取拓扑的技术。具体而言，我们展示了从与a）节点相对于称为锚点的一小组节点的最短跳距相对应的一小组测量中捕获的网络拓扑，或者b）一组随机节点对之间的成对跳距。这两个测量集可以与距离矩阵D相关联，距离矩阵D是拓扑的通用表示形式，其中条目包含两个节点之间的最短跳距。在基于锚的方法中，节点到一组M锚的最短跳距离构成了所谓的虚拟坐标（VC）矩阵。这是与锚节点对应的D列的子矩阵。随机成对测量对应于D元素的随机子集。所提出的技术依赖于基于扩展的稳健主成分分析的低秩矩阵完成方法，以提取未知元素。矩阵完成原理的应用依赖于这样的推测，即许多自然数据集固有地是低维的，因此相应的矩阵排名相对较低。我们证明这也适用于许多大型网络的D。因此，我们能够使用矩阵完成理论的结果来捕获拓扑。两种重要类型的图已用于评估所提出的技术，即无线传感器网络（WSN）图和社交网络图。对于WSN示例，我们使用拓扑保留图（TPM）（它是原始布局的同胚表​​示）来从VC矩阵的部分条目集中评估该技术的有效性。与现有的非中心化方法相比，基于双重中心化的方法用于评估VC的TPM。给出了边界上相距最远的随机锚点和节点的结果。获取拓扑的思想已扩展到社交网络链接预测。该结果的意义在于，随着隐私问题的增加，以VC矩阵形式或作为跳距矩阵获得数据变得困难。这种预测矩阵未知条目的方法为社交网络链接预测提供了一种新颖的方法，并得到大多数现实世界网络的距离矩阵自然是低排名的事实的支持。 4个不同的WSN和3个不同的社交网络。两个2D和两个3D网络已用于WSN，节点数量在500到1600之间。我们仅使用20％到40％的VC矩阵条目就可以获得随机锚和极端锚的精确TPM。平均误差量化了由于未知条目而在TPM中引入的误差。结果表明，即使缺少80％的条目，平均错误也大约在35％至45％之间; Facebook，Collaboration和Enron Email子网分别具有744、4158和3892个节点用于社交网络捕获。获得的结果非常有希望。跳距矩阵中80％的信息丢失，最大误差只有6％。跳距预测中的误差小于0.5跳。这也打开了通过其VC矩阵压缩网络表示的想法。

著录项

  • 作者

    Ramasamy, Sridhar.;

  • 作者单位

    Colorado State University.;

  • 授予单位 Colorado State University.;
  • 学科 Electrical engineering.;Computer engineering.
  • 学位 M.S.
  • 年度 2017
  • 页码 124 p.
  • 总页数 124
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号