Principal component analysis of link prediction scores to propose a binary classification model for the betweenness of edges in complex networks
摘要
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.