Estimating the Relative Importance of Nodes in Social Networks

• Item type: JInfP(1)
• 公開日: 2013-07-15
• タイトル: Estimating the Relative Importance of Nodes in Social Networks
• タイトル / 言語: en
• タイトル: Estimating the Relative Importance of Nodes in Social Networks
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [Special Issue on Applications and the Internet in Conjunction with Main Topics of SAINT 2012 (Invited Paper)] social networks, relative importance, path probability, random walk
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Department of Computer Science, Iowa State University
• 著者所属: Department of Computer Science, Iowa State University
• 著者所属: Department of Computer Science, Iowa State University
• 著者所属: Department of Computer Science, Iowa State University / School of Computer Science, Xi'an University of Posts and Telecommunications
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Iowa State University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Iowa State University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Iowa State University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Iowa State University / School of Computer Science, Xi'an University of Posts and Telecommunications
• 著者名: Heyong, Wang; CarlK.Chang; Hen-IYang; Yanping, Chen
• 著者名(英): Heyong, Wang; Carl, K.Chang; Hen-I, Yang; Yanping, Chen
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA00700121
• 書誌情報: Journal of information processing; 巻 21, 号 3, p. 414-422, 発行日 2013-07-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6652
• 出版者 / 言語: ja
• 出版者: 情報処理学会