首 页机构概况机构设置科研人才队伍合作交流研究生教育博士后图书馆创新文化党群园地院重点实验室彭桓武中心信息公开
  新闻动态
  您现在的位置:首页 > 新闻动态 > 科研动态
理论物理所在基于统计物理思想的大数据与社交网络研究方面取得进展
2018-07-13  【 】【打印】【关闭

  近年来线上社交网络(online social network)的规模不断扩大。比如微信和Facebook等的用户已经超过了十亿量级。在如此巨大的网络中如何精确并快速地量化某一用户在整个网络中的影响力,从而识别最有影响力的个体或群体,成为一个具有挑战性的问题。目前为止,大部分现有算法的时间复杂度至少为O(N)。也就是说,这些算法所花的时间随着网络规模的增大而迅速地增加。 

  最近, 中国科学院理论物理研究所金瑜亮副研究员(共同一作)及其合作者(中山大学胡延庆副教授、西南交通大学纪圣塨博士生、新加坡高性能计算所冯凌研究员、美国波士顿大学Gene Stanley教授、以色列巴依兰大学Shlomo Havlin教授)在国际顶级综合性期刊《美国科学院院刊》PNAS上发表了题为“Local structure can identify and quantify influential global spreaders in large scale social networks”的研究论文。该论文提出了一个称为PBGA的新算法,其理论时间复杂度与网络规模无关,从而解决了以上难题。 

  PBGA算法的提出受到了物理学中临界现象的启发:早在2002年,Newman就提出网络中的信息传播过程可以对应到一个经典的物理学问题--渗流相变(percolation transition)。渗流相变是一个标准的临界相变。对应于临界相变中的关联长度,该研究提出了传播半径的概念。基于网络中每个节点在传播半径范围内的局域网络结构信息,可以精确地度量该节点的传播能力。传播半径只与距离临界点的距离有关,而与网络规模无关。 

  在微博、FacebookQQTwitter等实际网络上的测试结果表明(见图一),PBGA算法的时间复杂度确实和网络规模基本无关。基于简单外推估算, 对于全局的Facebook网络,PBGA算法比经典贪心算法(NGA)将快约1010倍。 该算法不仅高效,而且克服了在规模较大的网络上无法得到完整的全局信息的困难,在病毒式营销(viral marketing)等电子商务领域有重要应用前景。 

   

  上图: PBGA算法和NGA算法在实际网络上(每个数据点代表一个网络)时间复杂度的测试结果。 

  文章链接http://www.pnas.org/content/early/2018/07/02/1710547115 

IE6.0浏览器,1024X768分辨率 版权所有 ? 中国科学院理论物理研究所
地址:北京市海淀区中关村东路55号 邮政编码:100190
京ICP备05002865号】 京公网安备1101080094号