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 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

f2: The influence of β on AUC and 〈B〉 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. 2, we show the dependence of and on under different . The CBCN and CBRA are used in Fig. 2(a–d), respectively. One can see that increases with , indicating that the links within the communities are easier to be predicted. The results of CBCN and CBRA are similar and the increment of is more significant when the community structure is more obvious (i.e. larger ). This result is consistent with a recent finding in ref. 43. In Fig. 2(a,b), the dashed lines mark the of the original CN and RA methods (without to adjust the ranking of the intra- and inter-community missing links). One can see that the of CBCN and CBRA can be respectively higher than the of CN and RA when is large.


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 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

f2: The influence of β on AUC and 〈B〉 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. 2, we show the dependence of and on under different . The CBCN and CBRA are used in Fig. 2(a–d), respectively. One can see that increases with , indicating that the links within the communities are easier to be predicted. The results of CBCN and CBRA are similar and the increment of is more significant when the community structure is more obvious (i.e. larger ). This result is consistent with a recent finding in ref. 43. In Fig. 2(a,b), the dashed lines mark the of the original CN and RA methods (without to adjust the ranking of the intra- and inter-community missing links). One can see that the of CBCN and CBRA can be respectively higher than the of CN and RA when is large.

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.