2015 · 43 citations · 38 references
Life SciencesBiologyComputational BiologyNetwork BiologyStructural BioinformaticsBiological NetworksGraph AlgorithmsGraph TheoryNetwork ModelingRandom WalksSocial Network AnalysisConfidence LevelGraph SimilarityNetwork SamplingRandom Walk AlgorithmsRandom Walks On GraphsRandom Walks On NetworksSampling
Estimating similarity between vertices is a fundamental issue in network analysis across various domains, such as social networks and biological networks. Methods based on common neighbors and structural contexts have received much attention. However, both categories of methods are difficult to scale up to handle large networks (with billions of nodes). In this paper, we propose a sampling method that provably and accurately estimates the similarity between vertices. The algorithm is based on a novel idea of random path. Specifically, given a network, we perform R random walks, each starting from a randomly picked vertex and walking T steps. Theoretically, the algorithm guarantees that the sampling size R = O(2ε-2 log2 T) depends on the error-bound ε, the confidence level (1 -- δ), and the path length T of each random walk.
38
Centrality in social networks conceptual clarification
Linton C. Freeman · Social Networks · 1978 · 16.9K citations
A Set of Measures of Centrality Based on Betweenness
Linton C. Freeman · Sociometry · 1977 · 10.2K citations