Physics – Physics and Society
Scientific paper
2011-06-03
PLoS ONE 6(11): e27028, 2011
Physics
Physics and Society
Scientific paper
10.1371/journal.pone.0027028
Identifying communities (or clusters), namely groups of nodes with comparatively strong internal connectivity, is a fundamental task for deeply understanding the structure and function of a network. Yet, there is a lack of formal criteria for defining communities and for testing their significance. We propose a sharp definition which is based on a significance threshold. By means of a lumped Markov chain model of a random walker, a quality measure called "persistence probability" is associated to a cluster. Then the cluster is defined as an "$\alpha$-community" if such a probability is not smaller than $\alpha$. Consistently, a partition composed of $\alpha$-communities is an "$\alpha$-partition". These definitions turn out to be very effective for finding and testing communities. If a set of candidate partitions is available, setting the desired $\alpha$-level allows one to immediately select the $\alpha$-partition with the finest decomposition. Simultaneously, the persistence probabilities quantify the significance of each single community. Given its ability in individually assessing the quality of each cluster, this approach can also disclose single well-defined communities even in networks which overall do not possess a definite clusterized structure.
No associations
LandOfFree
Finding and testing network communities by lumped Markov chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Finding and testing network communities by lumped Markov chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding and testing network communities by lumped Markov chains will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-223560