<p>The problem of quantifying edge betweenness in complex networks is computationally-intensive. We propose a novel idea of rather simply classifying the edges as those of high-betweenness or low-betweenness. We make use of the tendency of neighborhood-based link prediction techniques to highly score node pairs (including those connected through edges) that are already part of a dense sub graph. We compute link prediction scores (using four different neighborhood link prediction techniques) for all the node pairs in the network. Our hypothesis is the following: edges with high link prediction scores are likely to comprise of end vertices that part of the same dense sub graph, and hence are expected to be of low-betweenness. On the other hand, edges with relatively lower link prediction scores are likely to connect two different sub graphs (which would otherwise may not be even connected) and hence could be expected to be of high-betweenness. We conduct principal component analysis (PCA) of a link prediction scores dataset for all the node pairs in a network and compute a weighted average score (using the variances of the PCs as weights) for each node pair (including the edges in the network). We propose to categorize edges with negative values for the PCs-based weighted average link prediction score to belong to the class of "high-betweenness" edges and vice-versa. We evaluate the accuracy of our predictions using correlation studies.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Principal component analysis of link prediction scores to propose a binary classification model for the betweenness of edges in complex networks

  • Natarajan Meghanathan

摘要

The problem of quantifying edge betweenness in complex networks is computationally-intensive. We propose a novel idea of rather simply classifying the edges as those of high-betweenness or low-betweenness. We make use of the tendency of neighborhood-based link prediction techniques to highly score node pairs (including those connected through edges) that are already part of a dense sub graph. We compute link prediction scores (using four different neighborhood link prediction techniques) for all the node pairs in the network. Our hypothesis is the following: edges with high link prediction scores are likely to comprise of end vertices that part of the same dense sub graph, and hence are expected to be of low-betweenness. On the other hand, edges with relatively lower link prediction scores are likely to connect two different sub graphs (which would otherwise may not be even connected) and hence could be expected to be of high-betweenness. We conduct principal component analysis (PCA) of a link prediction scores dataset for all the node pairs in a network and compute a weighted average score (using the variances of the PCs as weights) for each node pair (including the edges in the network). We propose to categorize edges with negative values for the PCs-based weighted average link prediction score to belong to the class of "high-betweenness" edges and vice-versa. We evaluate the accuracy of our predictions using correlation studies.