Document Detail


Maximal-entropy random walk unifies centrality measures.
MedLine Citation:
PMID:  23368006     Owner:  NLM     Status:  Publisher    
Abstract/OtherAbstract:
This paper compares a number of centrality measures and several (dis-)similarity matrices with which they can be defined. These matrices, which are used among others in community detection methods, represent quantities connected to enumeration of paths on a graph and to random walks. Relationships between some of these matrices are derived in the paper. These relationships are inherited by the centrality measures. They include measures based on the principal eigenvector of the adjacency matrix, path enumeration, as well as on the stationary state, stochastic matrix, or mean first-passage times of a random walk. As the random walk defining the centrality measure can be arbitrarily chosen, we pay particular attention to the maximal-entropy random walk, which serves as a very distinct alternative to the ordinary (diffusive) random walk used in network analysis. The various importance measures, defined both with the use of ordinary random walk and the maximal-entropy random walk, are compared numerically on a set of benchmark graphs with varying mixing parameter and are grouped with the use of the agglomerative clustering technique. It is shown that centrality measures defined with the two different random walks cluster into two separate groups. In particular, the group of centrality measures defined by the maximal-entropy random walk does not cluster with any other measures on change of graphs' parameters, and members of this group produce mutually closer results than members of the group defined by the ordinary random walk.
Authors:
J K Ochab
Related Documents :
24129016 - Modeling mechanisms of persisting and resolving delay in language development.
21037886 - Seroprevalence of anaplasma marginale in 2 iowa feedlots and its association with morbi...
16298006 - Experimental and modelling study of different process modes for retroviral production i...
23720406 - Prediction of retention indices for frequently reported compounds of plant essential oi...
24920256 - A population of patient-specific adult acquired flatfoot deformity models before and af...
25137726 - Bias reduction for low-statistics pet: maximum likelihood reconstruction with a modifie...
Publication Detail:
Type:  JOURNAL ARTICLE     Date:  2012-12-12
Journal Detail:
Title:  Physical review. E, Statistical, nonlinear, and soft matter physics     Volume:  86     ISSN:  1550-2376     ISO Abbreviation:  Phys Rev E Stat Nonlin Soft Matter Phys     Publication Date:  2012 Dec 
Date Detail:
Created Date:  2013-2-1     Completed Date:  -     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  101136452     Medline TA:  Phys Rev E Stat Nonlin Soft Matter Phys     Country:  -    
Other Details:
Languages:  ENG     Pagination:  066109     Citation Subset:  -    
Affiliation:
Marian Smoluchowski Institute of Physics, Jagiellonian University, Reymonta 4, PL-30-059 Kraków, Poland.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  Propagation of fronts in the Fisher-Kolmogorov equation with spatially varying diffusion.
Next Document:  Spatial effects in real networks: Measures, null models, and applications.