Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLink-Prediction Enhanced Consensus Clustering for Complex Networks
136
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Many real networks that are inferred or collected from data are incomplete due to missing edges. Missing edges can be inherent to the dataset (Facebook friend links will never be complete) or the result of sampling (one may only have access to a portion of the data). The consequence is that downstream analyses that consume the network will often yield less accurate results than if the edges were complete. Community detection algorithms, in particular, often suffer when critical intra-community edges are missing. We propose a novel consensus clustering algorithm to enhance community detection on incomplete networks. Our framework utilizes existing community detection algorithms that process networks imputed by our link prediction based algorithm. The framework then merges their multiple outputs into a final consensus output. On average our method boosts performance of existing algorithms by 7% on artificial data and 17% on ego networks collected from Facebook.
rate research
Read More
Link prediction in complex network based on solely topological information is a challenging problem. In this paper, we propose a novel similarity index, which is efficient and parameter free, based on clustering ability. Here clustering ability is defined as average clustering coefficient of nodes with the same degree. The motivation of our idea is that common-neighbors are able to contribute to the likelihood of forming a link because they own some ability of clustering their neighbors together, and then clustering ability defined here is a measure for this capacity. Experimental numerical simulations on both real-world networks and modeled networks demonstrated the high accuracy and high efficiency of the new similarity index compared with three well-known common-neighbor based similarity indices: CN, AA and RA.
Community detection and link prediction are both of great significance in network analysis, which provide very valuable insights into topological structures of the network from different perspectives. In this paper, we propose a novel community detection algorithm with inclusion of link prediction, motivated by the question whether link prediction can be devoted to improving the accuracy of community partition. For link prediction, we propose two novel indices to compute the similarity between each pair of nodes, one of which aims to add missing links, and the other tries to remove spurious edges. Extensive experiments are conducted on benchmark data sets, and the results of our proposed algorithm are compared with two classes of baseline. In conclusion, our proposed algorithm is competitive, revealing that link prediction does improve the precision of community detection.
Networks can represent a wide range of complex systems, such as social, biological and technological systems. Link prediction is one of the most important problems in network analysis, and has attracted much research interest recently. Many link prediction methods have been proposed to solve this problem with various technics. We can note that clustering information plays an important role in solving the link prediction problem. In previous literatures, we find node clustering coefficient appears frequently in many link prediction methods. However, node clustering coefficient is limited to describe the role of a common-neighbor in different local networks, because it can not distinguish different clustering abilities of a node to different node pairs. In this paper, we shift our focus from nodes to links, and propose the concept of asymmetric link clustering (ALC) coefficient. Further, we improve three node clustering based link prediction methods via the concept of ALC. The experimental results demonstrate that ALC-based methods outperform node clustering based methods, especially achieving remarkable improvements on food web, hamster friendship and Internet networks. Besides, comparing with other methods, the performance of ALC-based methods are very stable in both globalized and personalized top-L link prediction tasks.
Over the years, quantifying the similarity of nodes has been a hot topic in complex networks, yet little has been known about the distributions of node-similarity. In this paper, we consider a typical measure of node-similarity called the common neighbor based similarity (CNS). By means of the generating function, we propose a general framework for calculating the CNS distributions of node sets in various complex networks. In particular, we show that for the Erd{o}s-R{e}nyi (ER) random network, the CNS distribution of node sets of any particular size obeys the Poisson law. We also connect the node-similarity distribution to the link prediction problem. We found that the performance of link prediction depends solely on the CNS distributions of the connected and unconnected node pairs in the network. Furthermore, we derive theoretical solutions of two key evaluation metrics in link prediction: i) precision and ii) area under the receiver operating characteristic curve (AUC). We show that for any link prediction method, if the similarity distributions of the connected and unconnected node pairs are identical, the AUC will be $0.5$. The theoretical solutions are elegant alternatives of the traditional experimental evaluation methods with nevertheless much lower computational cost.
Information entropy has been proved to be an effective tool to quantify the structural importance of complex networks. In the previous work (Xu et al, 2016 cite{xu2016}), we measure the contribution of a path in link prediction with information entropy. In this paper, we further quantify the contribution of a path with both path entropy and path weight, and propose a weighted prediction index based on the contributions of paths, namely Weighted Path Entropy (WPE), to improve the prediction accuracy in weighted networks. Empirical experiments on six weighted real-world networks show that WPE achieves higher prediction accuracy than three typical weighted indices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
