计算机应用 ›› 2013, Vol. 33 ›› Issue (06): 1553-1562.DOI: 10.3724/SP.J.1087.2013.01553

• 先进计算 • 上一篇    下一篇

加权社会网络中重要节点发现算法

韩忠明,苑丽玲,杨伟杰,万月亮   

  1. 北京工商大学 计算机与信息工程学院,北京 100048
  • 收稿日期:2012-12-10 修回日期:2013-02-19 出版日期:2013-06-01 发布日期:2013-06-05
  • 通讯作者: 韩忠明
  • 作者简介:韩忠明(1972-),男,山西文水人,副教授,CCF会员,博士,主要研究方向:互联网数据分析与挖掘、海量数据处理;苑丽玲(1992-),女(回族),北京人,主要研究方向:互联网数据分析与挖掘;杨伟杰(1980-),女,山东潍坊人,讲师,博士,主要研究方向:互联网数据分析与挖掘;万月亮(1973-),男,江西南昌人,讲师,博士,主要研究方向:多媒体数据挖掘。
  • 基金资助:

    国家自然科学基金资助项目(61170112);北京市属高等学校科学技术与研究生教育创新工程建设项目(PXM2012_014213_000037)

Algorithm for discovering influential nodes in weighted social networks

HAN Zhongming,YUAN Liling,YANG Weijie,WAN Yueliang   

  1. College of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048, China
  • Received:2012-12-10 Revised:2013-02-19 Online:2013-06-05 Published:2013-06-01
  • Contact: HAN Zhongming

摘要: 从社会网络中发现重要节点是一个很有意义的研究问题,目前多数重要节点发现方法是基于不加权网络。由于在社会网络中,节点之间的关系具有强弱差异,社会网络本质上是一个加权网络。对于加权社会网络中的重要节点发现较少有研究。利用节点交互,提出了节点间关系强度的一种度量方法,该方法考虑了节点局部有向交互特征与全局交互特征。利用节点的行为特征定义了节点活跃度。 采用关系强度作为边的权重,活跃度作为节点权重形成了加权社会网络。基于PageRank算法的思想,提出了两个改进算法,算法采用节点权值作为阻尼系数,在迭代式过程用边的权重代替了PageRank算法中的入边和。分别选择国内外具有代表性的2个社交网络上的数据集进行大量实验,并分别选择了不同的方法作为比较,实验结果表明改进算法能较好地发现加权社会网络中的重要节点。

关键词: 社会网络, 重要节点, 关系强度, 页面排序

Abstract: Key nodes discovery is very important for social network. Nowadays, most of methods of key nodes discovery do not take relationship strength of nodes into account. Social networks, in essence, are weighted networks because relationship strengths of nodes are different. In this paper, a new method to compute relationship strength of nodes based on node interactions was proposed, and the method combined local features with global features. A node activity degree using user behavior features was defined; as a result, social networks were represented as dual-weighted networks by taking relationship strength as edge weight and node activity as node weight. Based on PageRank algorithm, two improved algorithms were proposed. The node weights were used as damping coefficient, and the weight of the edges was used to compute importance of nodes during iterative process. Two datasets from different sources were selected and comprehensive experiments were conducted. The experimental results show that proposed algorithms can effectively discover key nodes in real social networks.

Key words: social network, key node, relationship strength, PageRank

中图分类号: