Limits...
Identifying and characterizing key nodes among communities based on electrical-circuit networks.

Zhu F, Wang W, Di Z, Fan Y - PLoS ONE (2014)

Bottom Line: Our method is applicable in both undirected and directed networks without a priori knowledge of the community structure.Our method bypasses the extremely challenging problem of partitioning communities in the presence of overlapping nodes that may belong to multiple communities.Due to the fact that overlapping and bridging nodes are of paramount importance in maintaining the function of many social and biological networks, our tools open new avenues towards understanding and controlling real complex networks with communities accompanied with the key nodes.

View Article: PubMed Central - PubMed

Affiliation: School of Systems Science, Beijing Normal University, Beijing, China.

ABSTRACT
Complex networks with community structures are ubiquitous in the real world. Despite many approaches developed for detecting communities, we continue to lack tools for identifying overlapping and bridging nodes that play crucial roles in the interactions and communications among communities in complex networks. Here we develop an algorithm based on the local flow conservation to effectively and efficiently identify and distinguish the two types of nodes. Our method is applicable in both undirected and directed networks without a priori knowledge of the community structure. Our method bypasses the extremely challenging problem of partitioning communities in the presence of overlapping nodes that may belong to multiple communities. Due to the fact that overlapping and bridging nodes are of paramount importance in maintaining the function of many social and biological networks, our tools open new avenues towards understanding and controlling real complex networks with communities accompanied with the key nodes.

Show MeSH
The usage of our method and in the LFR benchmark network.(a) The network is generated according to the rules of LFR benchmark. Nodes diameters indicate the current-flow centrality C, the color of each node is proportional to the index D. (b) The cumulative distribution function is used to identify the threshold of the C index. (c) the network can be separated by two categories according to the scatter plot, the upper right nodes can be considered as bridging nodes with high value of C and D. There are no overlapping nodes in this network.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0097021-g006: The usage of our method and in the LFR benchmark network.(a) The network is generated according to the rules of LFR benchmark. Nodes diameters indicate the current-flow centrality C, the color of each node is proportional to the index D. (b) The cumulative distribution function is used to identify the threshold of the C index. (c) the network can be separated by two categories according to the scatter plot, the upper right nodes can be considered as bridging nodes with high value of C and D. There are no overlapping nodes in this network.

Mentions: We test our method on the LFR benchmark introduced by Lancichinetti et al. [18]. In the LFR benchmark, the node degrees follow a power-law distribution with the exponent , and the sizes of the communities follow another power-law distribution with then exponent . To ensure a clear community structure, we set , , and . It can be intuitively understood that some nodes that connect two or more communities have large current values, corresponding to bridging nodes or overlapping nodes, as discussed before. Thus we need to introduce the index to distinguish these two types of nodes by using the current-distribution information for each node. The results demonstrate that some nodes whose current values are significantly larger than those of other nodes may be regarded as the two types of key nodes. As shown in Fig. 6, the network can be well separated into two categories. The nodes at the upper right of the scatter plot have relatively high values of both and , which indicates they have more internal edges than external edges. The nodes at the lower left are contained within communities and have few edges outside their communities. It can be claimed that there are no obvious overlapping nodes in this LFR benchmark, but it may contain some bridging nodes.


Identifying and characterizing key nodes among communities based on electrical-circuit networks.

Zhu F, Wang W, Di Z, Fan Y - PLoS ONE (2014)

The usage of our method and in the LFR benchmark network.(a) The network is generated according to the rules of LFR benchmark. Nodes diameters indicate the current-flow centrality C, the color of each node is proportional to the index D. (b) The cumulative distribution function is used to identify the threshold of the C index. (c) the network can be separated by two categories according to the scatter plot, the upper right nodes can be considered as bridging nodes with high value of C and D. There are no overlapping nodes in this network.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0097021-g006: The usage of our method and in the LFR benchmark network.(a) The network is generated according to the rules of LFR benchmark. Nodes diameters indicate the current-flow centrality C, the color of each node is proportional to the index D. (b) The cumulative distribution function is used to identify the threshold of the C index. (c) the network can be separated by two categories according to the scatter plot, the upper right nodes can be considered as bridging nodes with high value of C and D. There are no overlapping nodes in this network.
Mentions: We test our method on the LFR benchmark introduced by Lancichinetti et al. [18]. In the LFR benchmark, the node degrees follow a power-law distribution with the exponent , and the sizes of the communities follow another power-law distribution with then exponent . To ensure a clear community structure, we set , , and . It can be intuitively understood that some nodes that connect two or more communities have large current values, corresponding to bridging nodes or overlapping nodes, as discussed before. Thus we need to introduce the index to distinguish these two types of nodes by using the current-distribution information for each node. The results demonstrate that some nodes whose current values are significantly larger than those of other nodes may be regarded as the two types of key nodes. As shown in Fig. 6, the network can be well separated into two categories. The nodes at the upper right of the scatter plot have relatively high values of both and , which indicates they have more internal edges than external edges. The nodes at the lower left are contained within communities and have few edges outside their communities. It can be claimed that there are no obvious overlapping nodes in this LFR benchmark, but it may contain some bridging nodes.

Bottom Line: Our method is applicable in both undirected and directed networks without a priori knowledge of the community structure.Our method bypasses the extremely challenging problem of partitioning communities in the presence of overlapping nodes that may belong to multiple communities.Due to the fact that overlapping and bridging nodes are of paramount importance in maintaining the function of many social and biological networks, our tools open new avenues towards understanding and controlling real complex networks with communities accompanied with the key nodes.

View Article: PubMed Central - PubMed

Affiliation: School of Systems Science, Beijing Normal University, Beijing, China.

ABSTRACT
Complex networks with community structures are ubiquitous in the real world. Despite many approaches developed for detecting communities, we continue to lack tools for identifying overlapping and bridging nodes that play crucial roles in the interactions and communications among communities in complex networks. Here we develop an algorithm based on the local flow conservation to effectively and efficiently identify and distinguish the two types of nodes. Our method is applicable in both undirected and directed networks without a priori knowledge of the community structure. Our method bypasses the extremely challenging problem of partitioning communities in the presence of overlapping nodes that may belong to multiple communities. Due to the fact that overlapping and bridging nodes are of paramount importance in maintaining the function of many social and biological networks, our tools open new avenues towards understanding and controlling real complex networks with communities accompanied with the key nodes.

Show MeSH