Limits...
Extracting the globally and locally adaptive backbone of complex networks.

Zhang X, Zhang Z, Zhao H, Wang Q, Zhu J - PLoS ONE (2014)

Bottom Line: A complex network is a useful tool for representing and analyzing complex systems, such as the world-wide web and transportation systems.However, the growing size of complex networks is becoming an obstacle to the understanding of the topological structure and their characteristics.The links that have a small weight but are important from the view of topological structure are not belittled.

View Article: PubMed Central - PubMed

Affiliation: School of Economics and Management, Beijing University of Posts and Telecommunications, Beijing, China.

ABSTRACT
A complex network is a useful tool for representing and analyzing complex systems, such as the world-wide web and transportation systems. However, the growing size of complex networks is becoming an obstacle to the understanding of the topological structure and their characteristics. In this study, a globally and locally adaptive network backbone (GLANB) extraction method is proposed. The GLANB method uses the involvement of links in shortest paths and a statistical hypothesis to evaluate the statistical importance of the links; then it extracts the backbone, based on the statistical importance, from the network by filtering the less important links and preserving the more important links; the result is an extracted subnetwork with fewer links and nodes. The GLANB determines the importance of the links by synthetically considering the topological structure, the weights of the links and the degrees of the nodes. The links that have a small weight but are important from the view of topological structure are not belittled. The GLANB method can be applied to all types of networks regardless of whether they are weighted or unweighted and regardless of whether they are directed or undirected. The experiments on four real networks show that the link importance distribution given by the GLANB method has a bimodal shape, which gives a robust classification of the links; moreover, the GLANB method tends to put the nodes that are identified as the core of the network by the k-shell algorithm into the backbone. This method can help us to understand the structure of the networks better, to determine what links are important for transferring information, and to express the network by a backbone easily.

Show MeSH

Related in: MedlinePlus

An undirected artificial network.The numbers on the lines denote the weights of the links. Although the weight of link  is greater than that of link , link  is more important for node  than link  is, because link  is the only path through which node  can reach the remainder of the network.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0100428-g002: An undirected artificial network.The numbers on the lines denote the weights of the links. Although the weight of link is greater than that of link , link is more important for node than link is, because link is the only path through which node can reach the remainder of the network.

Mentions: The LANS method, for each node and for any of its neighbors , considers the fraction of non-zero links whose weights are less than or equal to , , where is the indicator function, is the number of neighbors of node , and is the normalized weight of link . If is less than a predetermined significance level , the link is locally significant and is included in the backbone network. Although both of the local methods do not belittle some links that have small weights from a global view by considering the importance of the links in each specific node, we argue that they could ignore some links that have small weights with respect to the topological aspect. They assume that, for a certain node, its neighboring links (the links that connect to the node) with larger weights are more important. In many cases, however, local and global topological structures of a link determine how important the link is. For example, in Figure 2, although the weight of link is greater than that of link , link is more important than link for node because is the path through which can reach most of the other nodes. From the prospective of information transfer, link can help node send or receive information more effectively than link can, because deleting link could cause more damage than deleting link for the information transfer of the network.


Extracting the globally and locally adaptive backbone of complex networks.

Zhang X, Zhang Z, Zhao H, Wang Q, Zhu J - PLoS ONE (2014)

An undirected artificial network.The numbers on the lines denote the weights of the links. Although the weight of link  is greater than that of link , link  is more important for node  than link  is, because link  is the only path through which node  can reach the remainder of the network.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0100428-g002: An undirected artificial network.The numbers on the lines denote the weights of the links. Although the weight of link is greater than that of link , link is more important for node than link is, because link is the only path through which node can reach the remainder of the network.
Mentions: The LANS method, for each node and for any of its neighbors , considers the fraction of non-zero links whose weights are less than or equal to , , where is the indicator function, is the number of neighbors of node , and is the normalized weight of link . If is less than a predetermined significance level , the link is locally significant and is included in the backbone network. Although both of the local methods do not belittle some links that have small weights from a global view by considering the importance of the links in each specific node, we argue that they could ignore some links that have small weights with respect to the topological aspect. They assume that, for a certain node, its neighboring links (the links that connect to the node) with larger weights are more important. In many cases, however, local and global topological structures of a link determine how important the link is. For example, in Figure 2, although the weight of link is greater than that of link , link is more important than link for node because is the path through which can reach most of the other nodes. From the prospective of information transfer, link can help node send or receive information more effectively than link can, because deleting link could cause more damage than deleting link for the information transfer of the network.

Bottom Line: A complex network is a useful tool for representing and analyzing complex systems, such as the world-wide web and transportation systems.However, the growing size of complex networks is becoming an obstacle to the understanding of the topological structure and their characteristics.The links that have a small weight but are important from the view of topological structure are not belittled.

View Article: PubMed Central - PubMed

Affiliation: School of Economics and Management, Beijing University of Posts and Telecommunications, Beijing, China.

ABSTRACT
A complex network is a useful tool for representing and analyzing complex systems, such as the world-wide web and transportation systems. However, the growing size of complex networks is becoming an obstacle to the understanding of the topological structure and their characteristics. In this study, a globally and locally adaptive network backbone (GLANB) extraction method is proposed. The GLANB method uses the involvement of links in shortest paths and a statistical hypothesis to evaluate the statistical importance of the links; then it extracts the backbone, based on the statistical importance, from the network by filtering the less important links and preserving the more important links; the result is an extracted subnetwork with fewer links and nodes. The GLANB determines the importance of the links by synthetically considering the topological structure, the weights of the links and the degrees of the nodes. The links that have a small weight but are important from the view of topological structure are not belittled. The GLANB method can be applied to all types of networks regardless of whether they are weighted or unweighted and regardless of whether they are directed or undirected. The experiments on four real networks show that the link importance distribution given by the GLANB method has a bimodal shape, which gives a robust classification of the links; moreover, the GLANB method tends to put the nodes that are identified as the core of the network by the k-shell algorithm into the backbone. This method can help us to understand the structure of the networks better, to determine what links are important for transferring information, and to express the network by a backbone easily.

Show MeSH
Related in: MedlinePlus