Group centrality is an extension of the classical notion of centrality for individuals, to make it applicable to sets of them. We perform a SWOT (strengths, weaknesses, opportunities and threats) analysis of the use of group centrality in semantic networks, for different centrality notions: degree, closeness, betweenness, giving prominence to random walks. Among our main results stand out the relevance and NP-hardness of the problem of finding the most central set in a semantic network for an specific centrality measure.
Random Walks and Semantic Networks. The motivation to address random walk centrality comes from works that have used the notion of random walks and related it with semantics. The work of @cite_11 compares the functioning of the human mind when searching for memories with a random walk in a semantic network, as both present a similar behavior. They conclude that these results can help clarify the possible mechanisms that could account for PageRank predicting the prominence of words in semantic memory. @cite_7 use random walks to determine the semantic relatedness of two elements. In particular, they use a personalized PageRank algorithm with a custom teleport vector. They conclude that random walk combined with personalized PageRank is a feasible and potentially fruitful mean of computing semantic relatedness for words and texts. @cite_15 introduce a new measure of lexical relatedness based on the divergence of the stationary distributions computed using random walks over graphs extracted from WordNet. All these works have been valuable sources of inspiration for our method.
@cite_15 @cite_7 @cite_11
2149801387 2144597083
Many systems for tasks such as question answering, multi-document summarization, and information retrieval need robust numerical measures of lexical relatedness. Standard thesaurus-based measures of word pair similarity are based on only a single path between those words in the thesaurus graph. By contrast, we propose a new model of lexical semantic relatedness that incorporates information from every explicit or implicit path connecting the two words in the entire graph. Our model uses a random walk over nodes and edges derived from WordNet links and corpus statistics. We treat the graph as a Markov chain and compute a word-specific stationary distribution via a generalized PageRank algorithm. Semantic relatedness of a word pair is scored by a novel divergence measure, ZKL, that outperforms existing measures on certain classes of distributions. In our experiments, the resulting relatedness measure is the WordNet-based measure most highly correlated with human similarity judgments by rank ordering at = .90. The concept of pagerank was first started as a way for determining the ranking of Web pages by Web search engines. Based on relations in interconnected networks, pagerank has become a major tool for addressing fundamental problems arising in general graphs, especially for large information networks with hundreds of thousands of nodes. A notable notion of pagerank, introduced by Brin and Page and denoted by PageRank, is based on random walks as a geometric sum. In this paper, we consider a notion of pagerank that is based on the (discrete) heat kernel and can be expressed as an exponential sum of random walks. The heat kernel satisfies the heat equation and can be used to analyze many useful properties of random walks in a graph. A local Cheeger inequality is established, which implies that, by focusing on cuts determined by linear orderings of vertices using the heat kernel pageranks, the resulting partition is within a quadratic factor of the optimum. This is true, even if we restrict the volume of the small part separated by the cut to be close to some specified target value. This leads to a graph partitioning algorithm for which the running time is proportional to the size of the targeted volume (instead of the size of the whole graph). In this paper, we analyze the efficiency of Monte Carlo methods for incremental computation of PageRank, personalized PageRank, and similar random walk based methods (with focus on SALSA), on large-scale dynamically evolving social networks. We assume that the graph of friendships is stored in distributed shared memory, as is the case for large social networks such as Twitter. For global PageRank, we assume that the social network has n nodes, and m adversarially chosen edges arrive in a random order. We show that with a reset probability of e, the expected total work needed to maintain an accurate estimate (using the Monte Carlo method) of the PageRank of every node at all times is [EQUATION]. This is significantly better than all known bounds for incremental PageRank. For instance, if we naively recompute the PageRanks as each edge arrives, the simple power iteration method needs [EQUATION] total time and the Monte Carlo method needs O(mn e) total time; both are prohibitively expensive. We also show that we can handle deletions equally efficiently. We then study the computation of the top k personalized PageRanks starting from a seed node, assuming that personalized PageRanks follow a power-law with exponent  q ln n random walks starting from every node for large enough constant q (using the approach outlined for global PageRank), then the expected number of calls made to the distributed social network database is O(k (R(1-) )). We also present experimental results from the social networking site, Twitter, verifying our assumptions and analyses. The overall result is that this algorithm is fast enough for real-time queries over a dynamic social network.