Limits...
The reconstruction of complex networks with community structure.

Zhang P, Wang F, Wang X, Zeng A, Xiao J - Sci Rep (2015)

Bottom Line: Link prediction is a fundamental problem with applications in many fields ranging from biology to computer science.In the literature, most effort has been devoted to estimate the likelihood of the existence of a link between two nodes, based on observed links and nodes' attributes in a network.We find that our method has high prediction accuracy and is very effective in reconstructing the inter-community links.

View Article: PubMed Central - PubMed

Affiliation: School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, P.R. China.

ABSTRACT
Link prediction is a fundamental problem with applications in many fields ranging from biology to computer science. In the literature, most effort has been devoted to estimate the likelihood of the existence of a link between two nodes, based on observed links and nodes' attributes in a network. In this paper, we apply several representative link prediction methods to reconstruct the network, namely to add the missing links with high likelihood of existence back to the network. We find that all these existing methods fail to identify the links connecting different communities, resulting in a poor reproduction of the topological and dynamical properties of the true network. To solve this problem, we propose a community-based link prediction method. We find that our method has high prediction accuracy and is very effective in reconstructing the inter-community links.

No MeSH data available.


The influence of β on AUC and 〈B〉 in four real networks.(a–d) are the results of CBCN and CBRA, respectively. The solid lines are the results of the community-based link prediction methods (CBCN and CBRA) and the dashed lines are the results of the classic link prediction methods (CN and RA). The results are averaged over  independent realizations.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4664866&req=5

f3: The influence of β on AUC and 〈B〉 in four real networks.(a–d) are the results of CBCN and CBRA, respectively. The solid lines are the results of the community-based link prediction methods (CBCN and CBRA) and the dashed lines are the results of the classic link prediction methods (CN and RA). The results are averaged over independent realizations.

Mentions: We also examine our method on four real networks: ZK is a social network in the zahcary karate club44, NS is the largest connected component of a co-authorship network of scientists who are publishing on the topic of network science45, Email is an email network of an university built by regarding each email address as a node and linking two nodes if there is an email communication between them46, C.elegans is a neural network of the worm Caenorhadities elegans with each neuron as a node and each synapse or gap junction as a link47. All of these real networks are widely used in the literature and the basic structural properties of them are listed in Table 1. Here we use them to examine our methods. Figure 3 shows the performance of the community-based link prediction methods on these real networks. One can see that the results are qualitatively the same as those in the GN-benchmark networks. In these real networks, as the community structure is not as obvious as the GN-benchmark, the effect of on is even smaller, especially after β > 0.1. However, the influence of on is still strong.


The reconstruction of complex networks with community structure.

Zhang P, Wang F, Wang X, Zeng A, Xiao J - Sci Rep (2015)

The influence of β on AUC and 〈B〉 in four real networks.(a–d) are the results of CBCN and CBRA, respectively. The solid lines are the results of the community-based link prediction methods (CBCN and CBRA) and the dashed lines are the results of the classic link prediction methods (CN and RA). The results are averaged over  independent realizations.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4664866&req=5

f3: The influence of β on AUC and 〈B〉 in four real networks.(a–d) are the results of CBCN and CBRA, respectively. The solid lines are the results of the community-based link prediction methods (CBCN and CBRA) and the dashed lines are the results of the classic link prediction methods (CN and RA). The results are averaged over independent realizations.
Mentions: We also examine our method on four real networks: ZK is a social network in the zahcary karate club44, NS is the largest connected component of a co-authorship network of scientists who are publishing on the topic of network science45, Email is an email network of an university built by regarding each email address as a node and linking two nodes if there is an email communication between them46, C.elegans is a neural network of the worm Caenorhadities elegans with each neuron as a node and each synapse or gap junction as a link47. All of these real networks are widely used in the literature and the basic structural properties of them are listed in Table 1. Here we use them to examine our methods. Figure 3 shows the performance of the community-based link prediction methods on these real networks. One can see that the results are qualitatively the same as those in the GN-benchmark networks. In these real networks, as the community structure is not as obvious as the GN-benchmark, the effect of on is even smaller, especially after β > 0.1. However, the influence of on is still strong.

Bottom Line: Link prediction is a fundamental problem with applications in many fields ranging from biology to computer science.In the literature, most effort has been devoted to estimate the likelihood of the existence of a link between two nodes, based on observed links and nodes' attributes in a network.We find that our method has high prediction accuracy and is very effective in reconstructing the inter-community links.

View Article: PubMed Central - PubMed

Affiliation: School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, P.R. China.

ABSTRACT
Link prediction is a fundamental problem with applications in many fields ranging from biology to computer science. In the literature, most effort has been devoted to estimate the likelihood of the existence of a link between two nodes, based on observed links and nodes' attributes in a network. In this paper, we apply several representative link prediction methods to reconstruct the network, namely to add the missing links with high likelihood of existence back to the network. We find that all these existing methods fail to identify the links connecting different communities, resulting in a poor reproduction of the topological and dynamical properties of the true network. To solve this problem, we propose a community-based link prediction method. We find that our method has high prediction accuracy and is very effective in reconstructing the inter-community links.

No MeSH data available.