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
Schematic network composed of 32 nodes and separated into 3 parts.Certain nodes connect the separate parts.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0097021-g001: Schematic network composed of 32 nodes and separated into 3 parts.Certain nodes connect the separate parts.

Mentions: Despite the algorithms developed for detecting communities in complex networks, precisely partitioning communities in many real scenarios is still a challenging problem because of the existence of special nodes that belong to different communities simultaneously, namely, overlapping nodes. Some approaches have been presented attempting to solve the community detection problem associated with overlapping nodes. For example, Palla et al. proposed a method based on clique percolation [9]. A community is defined by a set of nodes that can be visited by rolling a k clique over the network through other cliques with common nodes. Lancichinetti et al. proposed an algorithm to detect overlapping and hierarchical structures using a fitness function [10]. In contrast, fuzzy modularity concentrated on the probabilities of each node belonging to different modules [11]. Guimera et al. classified nodes based on their roles within communities, using their within-module degree and their participation coefficient to reflect their positions in their own module and with respect to other modules [12]. Nonetheless, to the best of our knowledge, we still lack an efficient method to identify “connectors” among communities without relying on accurate partition of communities. Here we classify connectors into two categories: overlapping node and bridging node. Overlapping nodes refer to the nodes that belong to two or more communities with a number of edges connecting to each community, e.g., node 12 in Fig. 1. Whereas bridging nodes refer to the nodes that belong to a single community but has a few connections to the other communities; in other words, their edges bridge their own communities and the others, e.g. node 16 and 24 in Fig. 1. The two types of nodes play key roles in the communications and interactions among different communities and server as “messengers”. Although we may find the two types of nodes in terms of partitioning communities by using the established methods, it is computational exhausted and considerably depends on the accuracy of detecting communities that has yet not been fully resolved. Despite some interesting methods based on synchronization processes to locate overlapping nodes [8], they are not available for bridging nodes. Moreover, algorithms and tools for tackling overlapping communities in directed networks are still lacking.


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

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

Schematic network composed of 32 nodes and separated into 3 parts.Certain nodes connect the separate parts.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0097021-g001: Schematic network composed of 32 nodes and separated into 3 parts.Certain nodes connect the separate parts.
Mentions: Despite the algorithms developed for detecting communities in complex networks, precisely partitioning communities in many real scenarios is still a challenging problem because of the existence of special nodes that belong to different communities simultaneously, namely, overlapping nodes. Some approaches have been presented attempting to solve the community detection problem associated with overlapping nodes. For example, Palla et al. proposed a method based on clique percolation [9]. A community is defined by a set of nodes that can be visited by rolling a k clique over the network through other cliques with common nodes. Lancichinetti et al. proposed an algorithm to detect overlapping and hierarchical structures using a fitness function [10]. In contrast, fuzzy modularity concentrated on the probabilities of each node belonging to different modules [11]. Guimera et al. classified nodes based on their roles within communities, using their within-module degree and their participation coefficient to reflect their positions in their own module and with respect to other modules [12]. Nonetheless, to the best of our knowledge, we still lack an efficient method to identify “connectors” among communities without relying on accurate partition of communities. Here we classify connectors into two categories: overlapping node and bridging node. Overlapping nodes refer to the nodes that belong to two or more communities with a number of edges connecting to each community, e.g., node 12 in Fig. 1. Whereas bridging nodes refer to the nodes that belong to a single community but has a few connections to the other communities; in other words, their edges bridge their own communities and the others, e.g. node 16 and 24 in Fig. 1. The two types of nodes play key roles in the communications and interactions among different communities and server as “messengers”. Although we may find the two types of nodes in terms of partitioning communities by using the established methods, it is computational exhausted and considerably depends on the accuracy of detecting communities that has yet not been fully resolved. Despite some interesting methods based on synchronization processes to locate overlapping nodes [8], they are not available for bridging nodes. Moreover, algorithms and tools for tackling overlapping communities in directed networks are still lacking.

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