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 κin on β* and AUC* in the GN-benchmark 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 100 independent realizations.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f4: The influence of κin on β* and AUC* in the GN-benchmark 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 100 independent realizations.

Mentions: In Fig. 4, we further investigate the influence of on and in the GN-benchmark networks. In Fig. 4(a,b), one can see that has an abrupt change after kin > 10. After this value, significantly increases with . This is because when the community structure is obvious (kin > 10), we don’t have to sacrifice too much and a large can already make close to the true value. In Fig. 4(c,d), we show the dependence of on . One can see that when is large, is very close to the of the original CN or RA. However, when is relatively small, can be much smaller than of CN or RA. This is because when is small, needs to be adjusted to a very small value in order to keep of the predicted links the same as the real links (as shown in Fig. 2). In this case, a large amount of needs to be sacrificed for a higher .


The reconstruction of complex networks with community structure.

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

The influence of κin on β* and AUC* in the GN-benchmark 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 100 independent realizations.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f4: The influence of κin on β* and AUC* in the GN-benchmark 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 100 independent realizations.
Mentions: In Fig. 4, we further investigate the influence of on and in the GN-benchmark networks. In Fig. 4(a,b), one can see that has an abrupt change after kin > 10. After this value, significantly increases with . This is because when the community structure is obvious (kin > 10), we don’t have to sacrifice too much and a large can already make close to the true value. In Fig. 4(c,d), we show the dependence of on . One can see that when is large, is very close to the of the original CN or RA. However, when is relatively small, can be much smaller than of CN or RA. This is because when is small, needs to be adjusted to a very small value in order to keep of the predicted links the same as the real links (as shown in Fig. 2). In this case, a large amount of needs to be sacrificed for a higher .

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.