近年来线上社交网络(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)。渗流相变是一个标准的临界相变。对应于临界相变中的关联长度，该研究提出了传播半径的概念。基于网络中每个节点在传播半径范围内的局域网络结构信息，可以精确地度量该节点的传播能力。传播半径只与距离临界点的距离有关，而与网络规模无关。 在微博、facebook、qq、twitter等实际网络上的测试结果表明(如图)，pbga算法的时间复杂度确实和网络规模基本无关。
基于简单外推估算，对于全局的facebook网络，pbga算法比经典贪心算法(nga)将快约1010倍。该算法不仅高效，而且克服了在规模较大的网络上无法得到完整的全局信息的困难，在病毒式营销(viral marketing)等电子商务领域有重要应用前景。 此项目得到中科院率先行动百人计划的资助。(来源：中国科学院理论物理研究所)
上一篇：
下一篇：