Estimating the Relative Importance of Nodes in Social Networks
スポンサーリンク
概要
- 論文の詳細を見る
In social networks, nodes usually represent people and edges represent the relationship and connections between people. Ranking how important the nodes are with respect to some query nodes has a lot of applications in social networks. More often, people are interested in finding the Top-k most "relatively important" nodes with respect to some query nodes. A major challenge in this area of research is to define a function for measuring the "relative importance" between two nodes. In this paper, we present a measure called path probability to represent the connection strength of a between the ending node and the starting node. We proposed a measure of relative importance by using the sum of the path probabilities of all the "important" paths between a node with respect to a query node. Another challenge of computing the relative importance is the scalability issue. Most popular solutions are random walk based algorithms which involve matrix multiplication, and therefore are computationally too expensive for large graphs with millions of nodes. In this paper, by defining the path probability and introducing a small threshold value to determine whether a path is important or significant, we are able to ignore a lot of unimportant nodes so as to be able to efficiently identify the Top-k most relatively important nodes to the query nodes. Experiments are conducted over several synthetic and real graphs. The results are encouraging, and show a strong correlation between our approach and the well known random walk with restart algorithm.
- Information and Media Technologies 編集運営会議の論文
Information and Media Technologies 編集運営会議 | 論文
- Optimal Balanced Semi-Matchings for Weighted Bipartite Graphs
- A Quantitative Evaluation Methodology of Interconnection Networks
- Proposal and Performance Evaluation of Hash-based Authentication for P2P Network
- Resolving Direct and Indirect Anaphora for Japanese Definite Noun Phrases
- Ring Signatures: Universally Composable Definitions and Constructions