Betweenness is a measure of the centrality of a node in a network, and is normally calculated as the fraction of shortest paths between node pairs that pass through the node of interest. Betweenness is, in some sense, a measure of the influence a node has over the spread of information through the network. By counting only shortest paths, however, the conventional definition implicitly assumes that information spreads only along those shortest paths. Here we propose a betweenness measure that relaxes this assumption, including contributions from essentially all paths between nodes, not just the shortest, although it still gives more weight to short paths. The measure is based on random walks, counting how often a node is traversed by a random walk between two other nodes. We show how our measure can be calculated using matrix methods, and give some examples of its application to particular networks.

@misc{newman2003measure, author = {Newman, M. E. J.}, title = {A measure of betweenness centrality based on random walks}, year = {2003}, url = {http://arxiv.org/abs/cond-mat/0309045}, keywords = {betweenness, centrality, measure, randomWalk, sna}, abstract = {Betweenness is a measure of the centrality of a node in a network, and is normally calculated as the fraction of shortest paths between node pairs that pass through the node of interest. Betweenness is, in some sense, a measure of the influence a node has over the spread of information through the network. By counting only shortest paths, however, the conventional definition implicitly assumes that information spreads only along those shortest paths. Here we propose a betweenness measure that relaxes this assumption, including contributions from essentially all paths between nodes, not just the shortest, although it still gives more weight to short paths. The measure is based on random walks, counting how often a node is traversed by a random walk between two other nodes. We show how our measure can be calculated using matrix methods, and give some examples of its application to particular networks.} }

%0 = misc %A = Newman, M. E. J. %B = } %C = %D = 2003 %I = %T = A measure of betweenness centrality based on random walks} %U = http://arxiv.org/abs/cond-mat/0309045

@article{park-2003-68, author = {Park, Juyong and Newman, M. E. J.}, title = {The origin of degree correlations in the Internet and other networks}, journal = {Physical Review E}, year = {2003}, volume = {68}, pages = {026112}, url = {doi:10.1103/PhysRevE.68.026112}, keywords = {correlations, degree, internet, measure, networks, origin, social} }

%0 = article %A = Park, Juyong and Newman, M. E. J. %D = 2003 %T = The origin of degree correlations in the Internet and other networks %U = doi:10.1103/PhysRevE.68.026112

@article{pastor2001dynamical, author = {Pastor-Satorras, R. and Vázquez, A. and Vespignani, A.}, title = {Dynamical and correlation properties of the Internet}, journal = {Physical Review Letters}, publisher = {APS}, year = {2001}, volume = {87}, number = {25}, pages = {258701}, url = {http://scholar.google.de/scholar.bib?q=info:KLiz1q2axUQJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0}, keywords = {analysis, correlation, degree, internet, measure, network} }

%0 = article %A = Pastor-Satorras, R. and Vázquez, A. and Vespignani, A. %D = 2001 %I = APS %T = Dynamical and correlation properties of the Internet %U = http://scholar.google.de/scholar.bib?q=info:KLiz1q2axUQJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0

@inproceedings{Adda98thegrace, author = {Adda, Gilles and Mariani, Joseph and Lecomte, Josette and Paroubek, Patrick and Rajman, Martin}, title = {The GRACE French Part-of-Speech Tagging Evaluation Task}, booktitle = {proceedings of the First International Conference on Language Resources and Evaluation (LREC}, year = {1998}, pages = {433--441}, keywords = {decision, measure, pos, precision, recall, tagging} }

%0 = inproceedings %A = Adda, Gilles and Mariani, Joseph and Lecomte, Josette and Paroubek, Patrick and Rajman, Martin %B = proceedings of the First International Conference on Language Resources and Evaluation (LREC %D = 1998 %T = The GRACE French Part-of-Speech Tagging Evaluation Task

@article{j1998collective, author = {Watts, Duncan J. and Strogatz, Steven H.}, title = {Collective dynamics of /`small-world/' networks}, journal = {Nature}, year = {1998}, volume = {393}, number = {6684}, pages = {440--442}, url = {http://dx.doi.org/10.1038/30918}, issn = {00280836}, keywords = {collective, dynamics, measure, networks, smallworld} }

%0 = article %A = Watts, Duncan J. and Strogatz, Steven H. %D = 1998 %T = Collective dynamics of /`small-world/' networks %U = http://dx.doi.org/10.1038/30918

This paper presents a new approach for measuring semantic similarity/distance between words and concepts. It combines a lexical taxonomy structure with corpus statistical information so that the semantic distance between nodes in the semantic space constructed by the taxonomy can be better quantified with the computational evidence derived from a distributional analysis of corpus data. Specifically, the proposed measure is a combined approach that inherits the edge-based approach of the edge counting scheme, which is then enhanced by the node-based approach of the information content calculation. When tested on a common data set of word pair similarity ratings, the proposed approach outperforms other computational models. It gives the highest correlation value (r = 0.828) with a benchmark based on human similarity judgements, whereas an upper bound (r = 0.885) is observed when human subjects replicate the same task.

@inproceedings{Jiang97taxonomySimilarity, author = {Jiang, J.J. and Conrath, D.W.}, title = {Semantic similarity based on corpus statistics and lexical taxonomy}, booktitle = {Proc. of the Int'l. Conf. on Research in Computational Linguistics}, year = {1997}, pages = {19--33}, url = {http://www.cse.iitb.ac.in/~cs626-449/Papers/WordSimilarity/4.pdf}, keywords = {1997, Conrath, Jiang, JiangConrath, folksonomy, lexical, measure, semantic, similarity, taxonomy}, abstract = {This paper presents a new approach for measuring semantic similarity/distance between words and concepts. It combines a lexical taxonomy structure with corpus statistical information so that the semantic distance between nodes in the semantic space constructed by the taxonomy can be better quantified with the computational evidence derived from a distributional analysis of corpus data. Specifically, the proposed measure is a combined approach that inherits the edge-based approach of the edge counting scheme, which is then enhanced by the node-based approach of the information content calculation. When tested on a common data set of word pair similarity ratings, the proposed approach outperforms other computational models. It gives the highest correlation value (r = 0.828) with a benchmark based on human similarity judgements, whereas an upper bound (r = 0.885) is observed when human subjects replicate the same task.} }

%0 = inproceedings %A = Jiang, J.J. and Conrath, D.W. %B = Proc. of the Int'l. Conf. on Research in Computational Linguistics %D = 1997 %T = Semantic similarity based on corpus statistics and lexical taxonomy %U = http://www.cse.iitb.ac.in/~cs626-449/Papers/WordSimilarity/4.pdf