MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}}); function MyAutoRun() {    var topp=$(window).height()/2; if($(window).height()>450){ jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); }  }    window.onload=MyAutoRun; $(window).resize(function(){ var bodyw=$win.width(); var _leftPaneInner_width = jQuery(".rich_html_content #leftPaneInner").width(); var _main_article_body = jQuery(".rich_html_content #main_article_body").width(); var rightw=bodyw-_leftPaneInner_width-_main_article_body-25;   var topp=$(window).height()/2; if(rightw<0||$(window).height()<455){ $("#nav-article-page").hide(); $(".outline_switch_td").hide(); }else{ $("#nav-article-page").show(); $(".outline_switch_td").show(); var topp=$(window).height()/2; jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); } }); 混合指标量子群智能社会网络事件检测方法
  软件学报  2016, Vol. 27 Issue (11): 2747-2762   PDF    
混合指标量子群智能社会网络事件检测方法
胡文斌, 王欢, 严丽平, 邱振宇, 肖雷, 杜博     
武汉大学 计算机学院, 湖北 武汉 430072
摘要: 社会网络错综复杂,如果能够及时发现和预测当前网络可能发生的重大事件并采取有效的处置策略,将具有重大意义.链路预测的理论框架和评价方法为社会网络事件检测提供了一条有效途径.目前,链路预测的研究工作大多针对特定网络提出相似性指标,试图取得更高的链路预测精度.这些研究存在如下问题:(1)不同的相似性指标适用于不同的网络,不具有普适性;(2)独立的相似性指标无法全面反映网络演化的多样性和复杂性;(3)链路预测时未考虑网络演化过程中可能出现波动,无法进行事件检测.基于上述问题,提出一种社会网络事件检测的混合指标群智能方法IndexEvent,由最佳权重算法OWA(optimal weight algorithm)和波动检测算法FDA(fluctuationdetection algorithm)组成,可以评价不同网络的演化波动,发现网络波动异常,进行事件检测.主要工作如下:(1)提出了混合指标,并证明了基于混合指标的链路预测算法可以取得更高的预测精度;(2)基于量子粒子群算法提出了最佳权重算法OWA,以高效地确定不同网络的最佳混合指标;(3)提出了一种网络波动检测算法FDA,定量评价不同时段网络演化的波动程度,并在考虑微观因素的基础上进行改进.对不同特征的网络进行实验,结果表明,IndexEvent方法能够准确地反映事件造成的网络演化波动,有效地检测事件.
关键词: 量子粒子群     事件检测     链路预测     社会网络     网络演化     网络波动性评价    
Hybrid Quantum Swarm Intelligence Indexing for Event Detection in Social Networks
HU Wen-Bin, WANG Huan, YAN Li-Ping, QIU Zhen-Yu, XIAO Lei, DU Bo     
Computer School, Wuhan University, Wuhan 430072, China
Foundation item: National Program on Key Basic Research Project of China (973) (2012CB719905);National Natural Science Foundation of China (61572369, 61471274);National Natural Science Foundation of Hubei Province (2015CFB423);Wuhan Major Science and Technology Program (2015010101010023)
Abstract: In complicated social networks, discovering or predicting important events is significant. The theoretical framework and evaluation methods of link prediction offer an effective solution for detecting events in social networks. Most of the current research focuses on proposing different similarity indexes to achieve higherlink prediction accuracy. However this type of approach has following problems:(1) Because different similarity indexes are designed for different networks, they are not universal; (2) The independent similarity index is difficult to reflect diversity and complexity of real network evolutions; (3) Without considering the fluctuation in the network evolution, the link prediction cannot detect events. To solve these problems, this paper proposes a swarm intelligence method based on mixed indexes (IndexEvent), which can evaluate fluctuations and detect events in social networks. The main work is as follow:(1) A proof is provided on the proposed mixed indexes that the link prediction algorithm based on mixed indexes can achieve a higher accuracy; (2) Based on the quantum-behaved particle swarm algorithm, an optimal weight algorithm (OWA) is developed to determine best mixed indexes for different networks efficiently; (3) A fluctuation detection algorithm (FDA) is designed to quantitatively estimates fluctuations in network evolutions at different periods. And micro factors are taken into account to improve FDA. The results of the experiments show that IndexEvent can effectively reflect evolution fluctuations and detect events.
Key words: quantum particle swarm     event detection     link prediction     social network     network evolution     network fluctuation evaluation    

社会网络是指社会不同个体成员之间因互动而形成的相对稳定的关系体系.社会网络事件检测通常通过检测各个时段的网络演化的变化,分析出网络演化的异样,从而检测出当前网络发生的事件,提出干预和处置策略[1].社会网络事件检测具有广泛的应用场景和极大的实用价值,例如,它可以分析犯罪网络中核心头目的更替、预测公司人员结构调整影响、分析股票波动,进行舆情检测等[2].

在真实的社会网络中,很多事件的发生都有可能导致网络偏离正常的演化机制,产生异常的网络演化波动.如何基于当前复杂的社会网络,快速、准确地检测出当前网络发生的重大事件,评估不同事件产生的影响,并且提出有效的处置策略,是社会网络事件检测面临的重大挑战.目前,社会网络事件检测的主要方法如下:(1) 直接建立网络演化模型,调整模型参数,使产生的网络更加接近真实网络,仿真各个时间段的网络结构,发现异常网络结构.比较典型的模型有Watts-Strogatz(WS)小世界模型[3]、Barabási-Albert(BA)无标度模型[4].但这些网络演化模型都处于理论探究阶段,尚不能应用在真实网络上.(2) 基于网络结构图的分析方法进行事件检测,涉及图形数据挖掘、数理统计、机器学习等理论,常见方法有图形模式识别[5]、图形相似度比较[6]、统计过程控制[7]、扫描统计[8].但是这些方法计算量巨大,适用范围有限,忽视了网络演化的动态性.

本文借助链路预测的理论框架和评价方法提出了一种新的社会网络事件检测思路,量化网络演化波动,发现异常波动,从而实现事件检测.链路预测是指利用网络的结构或节点的属性信息来预测未产生连边的两节点间产生连边的可能性.常见的链路预测方法有基于马尔可夫链或机器学习的方法[9]和基于似然分析的方法[10],但这两种方法都存在计算复杂度过高的问题.与这两类方法相比,基于相似性的链路预测方法更简单、高效,并且通常能够取得很好的预测效果.具体步骤:利用某种相似性指标来计算当前时刻不存在连边的两节点之间产生连边的可能性得分,然后根据每条边的得分值进行降序排列,选取排列靠前的一定数目的边作为预测结果输出.目前,基于相似性的链路预测研究侧重于提出新的相似性指标来取得更好链路预测精度[11].然而,真实网络的演化机制纷繁复杂[12],很难通过基于单一的相似性指标去准确刻画.现有的相似性指标都是针对具有特定拓扑结构性质的网络才可能有最佳效果,缺乏普适性.同时,现有的相似性指标之间的协作关系缺乏探究,每个相似性指标都被独立用于链路预测.

为了解决独立相似性指标的精度不足、缺乏普适性和协作的问题,本文提出了混合指标,并在此基础上提出了一种社会网络事件检测方法IndicesEvent,包含最佳权重算法OWA(optimal weight algorithm)和波动检测算法FDA(fluctuation detection algorithm).OWA可以自动高效地确定不同社会网络对应的最佳混合指标.同时,FDA借助最佳混合指标对不同时刻网络演化的波动进行量化评价,检测重大事件的发生,并在考虑微观因素的基础上进行改进FDA.综上,本文主要工作可以总结如下:

(1) 提出OWA来高效地确定混合指标中各单位指标的最佳权重,可以得到不同社会网络对应的最佳混合指标.解决现有链路预测的相似性指标缺乏普适性、相互之间独立无法协作预测等问题;

(2) 提出一种网络波动检测算法FDA,并在考虑节点微观演化规律因素的基础上进行改进,解决链路预测无法检测网络演化波动异常的问题;

(3) 结合OWA和FDA提出一种通用的社会网络事件检测方法IndexEvent,可以准确地检测出网络中发生的重大事件,并对事件影响进行量化评价.

本文第1节介绍相关研究工作.第2节详细介绍IndexEvent方法,并借助WS小世界模型的实例、BA无标度模型的实例来提出最佳权重算法OWA和网络波动检测算法FDA.第3节通过真实的通信网络和邮件网络来确定验证IndexEvent方法的效果,并分析实验结果.第4节是结论及展望.

1 相关工作

在链路预测方面,Sarukkai[13]基于马尔可夫链进行网络的链路预测分析.Zhu等人[14]率先在自适应性网站的预测中使用基于马尔可夫链的预测方法.Newman等人[15]认为很多网络的连接可以反映内在的层次结构,提出了一种最大似然估计的算法进行链路预测,该方法在处理像草原食物链这样具有明显网络层次组织的网络时具有较好的精度.Guimera等人[16]提出一种基于随机分块模型的链路预测方法,该模型中,节点被分为若干集合,两个节点间连接的概率只与相应的集合相关.该方法不仅可以预测缺失边,还可以预测网络的错误链接,例如纠正蛋白质相互作用网络中的错误链接.然而,基于最大似然的方法[15, 16]计算复杂度太高,不适合于在规模大的网络中应用.Liben-Nowell等人[17]提出了基于网络拓扑结构的相似性定义方法,把指标分为基于节点和基于路径两类,并分析了部分指标在社会合作网络中链路预测的效果.Kleinberg等人[11]通过对比多种相似性指标在链路预测中的表现(共同邻居[18]、Jaccar系数[19]、Adamic/Adar[20]、优先链接[21]等),系统地阐述了链路预测问题.Lichtenwalter等人[22]提出了一种引入监督学习的链路预测方法,效果比无监督学习的方法提高了30%以上.Symeonidis等人[23]通过引入多条路径信息提出了多路谱聚类方法,提高了在社会网络和蛋白质作用网络上的链路预测精度.Huang等人[24]在得到节点的直接相似性后,利用协同过滤技术对相似性指标进行一轮加权处理,取得了较好的效果.Rao等人[25]为了将链路预测应用到大规模网络,实现了基于MapRe duce的计算模型的链路预测算法.此外,文献[26-29]考虑两端节点度的影响,从不同角度提出了其他相似性指标,但是大多集中在链路预测自身机制探讨或提高预测精度上,缺乏实际应用研究.

在社会网络事件检测方面,Noble等人[30]提出了通过迭代比较发现异常网络结构的方法,以及通过子结构条件熵来量化图形结构的异常程度.但是该方法主要注重于理论研究,实际计算非常复杂.Papadimitriou[6]面向较大规模的Web网络,充分考虑了节点和边的重要性,通过检测网络异常来判断服务器、爬虫程序等是否有异常发生.McCulloh等人[7]提出了专门的社会网络变化检测方法,有效地屏蔽正常波动带来的干扰,将网络实质变化从正常波动中分离出来,但是这种检测方法要求网络参数满足正态分布,致使其应用范围受到极大的限制. Priebe等人[31]采用扫描统计量方法对邮件网络进行检测,发现了网络中的“震荡”区域.Wan等人[8]通过分别检测网络节点网络参数的变化和相对于社团通联结构的变化,发现邮件网络的异常事件.但Priebe[31]和Wan[8]的工作由于要计算的统计量过多,导致计算量巨大.Wu等人[32]和Baruah等人[33]提出的网络相似性计算方法都由于没有统一各种因素的影响,导致最终结果不具参考性.Qiao等人[34]对犯罪成员的邮件网络进行分析,挖掘出犯罪组织的主要成员,发现异常通信事件.

综上,现有的社会网络的事件检测问题仍缺乏有效的解决方案.本文提出通用的OWA来寻找最匹配当前网络的链路预测指标和FDA来精确检测网络波动性异常,并且结合OWA和FDA构建了一种高效的社会网络事件检测方法IndexEvent.

2 IndexEvent方法框架

真实的社会网络具有统一性、多样性和复杂性的特点,很难预知一个真实网络的演化机制,并构建合适的网络演化模型进行分析.链路预测和网络演化具有内在一致性[35],借助社会网络数据集得到的不同时段网络拓扑结构信息,利用链路预测可以评价不同时段网络演化的波动.本文提出的IndexEvent方法依次对各时间段的演化波动进行定量评价,通过评价结果去检测网络事件的发生.IndexEvent方法框架如图 1所示,它包含算法OWA和FDA.

Fig. 1 Framework of method IndexEvent 图 1 IndexEvent方法框架

(1) 基于量子粒子群算法QPSO(quantum-behaved particle swarm algorithm)的OWA能够高效地确定给定时段网络演化的最佳混合指标.

(2) FDA算法借助最佳混合指标,量化不同时段的网络演化波动,得到事件检测序列.事件检测序列中事件检测值越低,其对应时段的网络演化波动越大,发生事件的可能性也就越大.

IndexEvent方法的实现步骤如图 2所示,以OWA和OWA为基础实现IndexEvent方法的事件检测.

Fig. 2 Implementation steps of method IndexEvent 图 2 IndexEvent方法的实现步骤

2.1 算法 OWA

第2.1.1节提出了混合指标的概念.第2.1.2节详细介绍了OWA如何确定最佳混合指标.同时,在第2.1.1节和第2.1.2节中,我们都会结合WS小世界网络进行详细解释.

2.1.1 混合指标

基于相似性指标的链路预测方法是一种简约、高效的方法,目前已有许多节点相似指标被提出,常见相似性指标及其计算方法见表 1.

Table 1 Common similarity indexs 表 1 常见的相似性指标

通过相似性指标计算出的两个节点之间相似性得分越大,它们之间存在连边的可能性就越大.其中,S(i,j)表示节点i与节点j的相似性得分,G(i)表示节点i的邻居所组成的集合,节点i的度为k(i)=|G(i)|.一个真实网络的演化往往交杂多种网络演化机制,基于一种相似性指标的链路预测算法很难全面地刻画真实网络的演化.

为了更全面地刻画真实网络的演化,本文基于现有的节点相似性指标提出了一种混合指标的概念,称为MixSimIndex,用公式(1) 表示.

$\begin{align} & MixSimIndex=F({{w}_{1}},...,{{w}_{m}},...,{{w}_{n}},SimInde{{x}_{1}},...,SimInde{{x}_{m}},...,SimInde{{x}_{n}}), \\ & SimInde{{x}_{m}}\in \phi ,\sum\limits_{m=1}^{n}{{{w}_{m}}}=1 \\ \end{align}$ (1)

其中,SimIndexm是特定的相似性指标,称为MixSimIndex的单位指标.wm为对应的单位指标SimIndexm的权重.n是所选定的相似性指标的数目,即单位指标的数目.φ代表相似性指标集合,以后研究中提出的新的相似性指标也可以不断加入该集合中.单位指标都源于集合φ.F表示混合指标MixSimIndex,MixSimIndex和各单位指标及权重之间的函数关系,增强了混合指标形式的灵活性.

$MixSimIndex=\sum\limits_{m=1}^{n}{{{w}_{m}}\times SimInde{{x}_{m}}},SimInde{{x}_{m}}\in \phi ,\sum\limits_{m=1}^{n}{{{w}_{m}}}=1$ (2)

本文采用公式(2) 表示MixSimIndex,集合φ只考虑表 1中指出的8种相似性指标.例如,MixSimIndex=0.7x AA+0.1xSA+0.2xCN.基于MixSimIndex可计算节点对ij的相似性得分为

$S(i,j)=0.7\times \sum\limits_{z\in \Gamma (i)\cap \Gamma (j)}{\frac{1}{{{\lg }^{k(z)}}}}+0.1\times \frac{|\Gamma (i)\cap \Gamma (j)|}{\sqrt{k(i)\times k(j)}}+0.2\times |\Gamma (i)\cap \Gamma (j)|$

同时,由公式(2) 可知,独立的相似性指标(如表 1中的CN,JA,PA,SO,AA,HPI,SA,LNH等)属于MixSimIndex的特例.例如,集合φ中只有CN被选作为单位指标,则CN的权重一定是1,MixSimIndex=CN,此时,混合指标就等同于独立的相似性指标 .

链路预测算法精度的衡量指标主要有AUC[36]、精确度(precision)[37]和排序分(ranking score)[38].它们对精度判定的侧重点不同.Precision只考虑排在前L位的边是否准确预测,而Ranking Score更多地考虑了所预测的边的排序.AUC是最常用的一种衡量指标,它从整体上衡量算法的精度.

本文选取AUC作为衡量指标,其定义用公式(3) 表示:

$AUC=\frac{{n}'+0.5{n}''}{n}$ (3)

其中,n表示比较的次数,n'表示从测试集中随机选择边的得分大于从不存在边构成集合中随机选择边的得分的次数,n"表示相等的次数.AUC反映了链路预测算法的预测精度,值越大,说明所对应的指标越好,越符合当前的网络演化机制.如果所有节点对的得分是随机产生的,则理想情况下,AUC=0.5.当AUC>0.5时,才能表明相似性指标的有效性 ,所以我们规定φ中满足AUC大于0.5的相似性指标才能被选为单位指标.

Watts等人提出了著名的WS小世界网络[3],它介于规则网络和随机网络之间.为了更好地解释混合指标,我们构造WS小世界网络实例:生成200个节点,每个节点有4个近邻居,以0.3的概率随机化重连边.所构造实例特性见表 2.

Table 2 Structure of WS small world network characteristics 表 2 构造的WS小世界网络特性

利用表 2中的相似性指标对所构造的WS小世界网络实例进行链路预测,当前网络存在的所有的边作为测试集合,当前网络所有节点间不存在的边构成不存在边集合.同时,由于所构建的WS小世界网规模较小,为了更好地说明混合指标的有效性,本节将测试集和不存在边集合中的所有边都进行一一比较,防止边选取时的随机性导致AUC的波动.基于表 2中各相似性指标链路预测算法对应的AUC值比较见表 3.

Table 3 AUC values of common similarity indexs 表 3 常见相似性指标AUC值

由于表 3中的8种相似性指标的AUC值都大于0.5,所以我们可以灵活地选取一定数目的指标作为混合指标的单位指标.以单位指标组合AA和HPI,CN和PA为例,如表 4所示,当MixSimIndex为0.5xAA+0.5xHP I和0.9xCN+0.1xPA时,它们得到的AUC值都高于表 3中的8个独立指标;但是当MixSimIndex为0.1xAA+0.9xHPI时,它们得到的AUC值低于单独相似性指标AA的AUC值;当MixSimIndex为0.1xCN+0.9xPA时,它们得到的AUC值低于表 3中的8个单独相似性指标.由表 4可知,混合指标的存在是有意义的.但并不是所有的混合指标都能取得比常见独立相似性指标更高的链路预测精度,只有当混合指标中的单位指标被赋予合适权重的情况下,才能取得比独立相似性指标更高的链路预测精度.

Table 4 Example of hybrid index AUC value 表 4 混合指标AUC值举例

2.1.2 OWA的实现

上一节已经论证了混合指标的可行性,混合指标的优劣与其各单位指标的权重息息相关.如果各单位指标权重确定后的混合指标的链路预测效果最佳,则称其为最佳混合指标,即最符合当前网络演化机制的混合指标.如何快速确定最佳混合指标,将是本节致力解决的问题.

量子信息的基本存储单元是量子比特,|0>和|1>表示一个量子比特的两种极化状态[39].量子比特状态可表示为Pic|0>+Pisb|1>,PicPis分别表示量子位状态|0>和|1>的概率幅.Tang等人[40]将量子机制融入到原始粒子群优化算法(particle swarms optimization,简称PSO)[41]中,提出了量子粒子群优化算法(quantum-behaved particle swarm optimization,简称QPSO).与原始PSO相比,QPSO需要设置的参数减少,并且有更强的寻优能力.本文提出基于QPSO的算法OWA快速确定混合指标中各单位指标的最佳权重,生成最佳混合指标.

假设已确定最佳混合指标中的有n单位指标SimIndex1,SimIndex2,...,SimIndexn,它们各自对应的权重为w1,w2,...,wn,可组成权重数组W=(w1,w2,...,wn).fitness(MixSimIndex(W))表示权重数组W对应的混合指标的适应度值,即在权重数组W=(w1,w2,...,wn)对应的混合指标$MixSimIndex=\sum\limits_{m=1}^{n}{{{w}_{m}}\times SimInde{{x}_{m}}}$上进行链路预测最终得到的衡量指标值.适应度值越大,则表示权重数组W生成的混合指标越优秀.算法OWA具体可分为3个步骤:

(1) 产生携带权重数组的初始量子粒子群:量子粒子群中每个量子态粒子编码方式如公式(4) 所示:

${{P}_{i}}=\left[ \left| \begin{matrix} \cos ({{\theta }_{i1}}) \\ \sin ({{\theta }_{i1}}) \\ \end{matrix} \right|\left. \begin{matrix} \cos ({{\theta }_{i2}}) \\ \sin ({{\theta }_{i2}}) \\ \end{matrix} \right|\left. \begin{matrix} ... \\ ... \\ \end{matrix} \right|\left. \begin{matrix} \cos ({{\theta }_{in}}) \\ \sin ({{\theta }_{in}}) \\ \end{matrix} \right| \right]$ (4)

其中,θij=2π×rnd,rnd为(0,1) 之间的随机数;i=1,2,…,m,j=1,2,…,n,m是量子粒子群中粒子数目,粒子数目越多,越能增加初始化时权重数组的差异性;n表示最佳混合指标中的有n单位指标.每个量子态粒子占据的两个位置分别对应于概率幅PisPic,可用公式(5) 和公式(6) 表示:

${{P}_{is}}=(sin({{\theta }_{i}}_{1}),sin({{\theta }_{i}}_{2}),\ldots ,sin({{\theta }_{in}}))$ (5)
${{P}_{ic}}=(cos({{\theta }_{i}}_{1}),cos({{\theta }_{i}}_{2}),\ldots ,cos({{\theta }_{in}}))$ (6)

每个量子态粒子的概率幅PisPic可以通过公式(7) 和公式(8) 转化为对应的权重数组WisWic,W可以取值为WisWic:

${{W}_{is}}=\left( \frac{\sin ({{\theta }_{i1}})}{\sum\limits_{m=1}^{n}{\sin ({{\theta }_{im}})}},\frac{\sin ({{\theta }_{i2}})}{\sum\limits_{m=1}^{n}{\sin ({{\theta }_{im}})}},...,\frac{\sin ({{\theta }_{in}})}{\sum\limits_{m=1}^{n}{\sin ({{\theta }_{im}})}} \right)$ (7)
${{W}_{ic}}=\left( \frac{\cos ({{\theta }_{i1}})}{\sum\limits_{m=1}^{n}{\cos ({{\theta }_{im}})}},\frac{\cos ({{\theta }_{i2}})}{\sum\limits_{m=1}^{n}{\cos ({{\theta }_{im}})}},...,\frac{\cos ({{\theta }_{in}})}{\sum\limits_{m=1}^{n}{\cos ({{\theta }_{im}})}} \right)$ (8)

(2) 权重数组更新:权重数组的更新是由概率幅PisPic的更新实现的.每次迭代,都将PisPic通过公式(9)得到${{\bar{P}}_{is}}$和${{\bar{P}}_{ic}},$然后${{P}_{is}}={{\bar{P}}_{is}},{{P}_{ic}}={{\bar{P}}_{ic}},$实现更新,继续进行下次迭代:

$\left\{ \begin{align} & {{{\tilde{P}}}_{ic}}=(\cos ({{\theta }_{i1}}(t)+\text{ }\!\!\Delta\!\!\text{ }{{\theta }_{i1}}(t+1)),...,\cos ({{\theta }_{in}}(t)+\text{ }\!\!\Delta\!\!\text{ }{{\theta }_{in}}(t+1))) \\ & {{{\tilde{P}}}_{is}}=(\sin ({{\theta }_{i1}}(t)+\text{ }\!\!\Delta\!\!\text{ }{{\theta }_{i1}}(t+1)),...,\sin ({{\theta }_{in}}(t)+\text{ }\!\!\Delta\!\!\text{ }{{\theta }_{in}}(t+1))) \\ \end{align} \right.$ (9)

其中,

$\begin{matrix} \text{ }\!\!\Delta\!\!\text{ }{{\theta }_{ij}}(t+1)=w\text{ }\!\!\Delta\!\!\text{ }{{\theta }_{ij}}(t)+{{c}_{1}}{{r}_{1}}(\text{ }\!\!\Delta\!\!\text{ }{{\theta }_{l}})+{{c}_{2}}{{r}_{2}}(\text{ }\!\!\Delta\!\!\text{ }{{\theta }_{g}}), \\ \text{ }\!\!\Delta\!\!\text{ }{{\theta }_{l}}=\left\{ \begin{array}{*{35}{l}} 2\pi +{{\theta }_{ilj}}+{{\theta }_{ij}}({{\theta }_{ilj}}-{{\theta }_{ij}}<-\pi ) \\ {{\theta }_{ilj}}-{{\theta }_{ij}}(-\pi \le {{\theta }_{ilj}}-{{\theta }_{ij}}\le -\pi ) \\ {{\theta }_{ilj}}-{{\theta }_{ij}}-2\pi ({{\theta }_{ilj}}-{{\theta }_{ij}}>\pi ) \\ \end{array} \right., \\ \text{ }\!\!\Delta\!\!\text{ }{{\theta }_{g}}=\left\{ \begin{array}{*{35}{l}} 2\pi +{{\theta }_{gj}}+{{\theta }_{ij}}({{\theta }_{gj}}-{{\theta }_{ij}}<-\pi ) \\ {{\theta }_{gj}}-{{\theta }_{ij}}(-\pi \le {{\theta }_{gj}}-{{\theta }_{ij}}\le -\pi ) \\ {{\theta }_{gj}}-{{\theta }_{ij}}-2\pi ({{\theta }_{gj}}-{{\theta }_{ij}}>\pi ) \\ \end{array} \right.. \\ \end{matrix}$

(3) 权重数组变异处理:原始的PSO算法易陷入混合指标局部最优,主要原因在于搜索过程中权重数组的多样性的丢失.算法OWA借助量子非门实现变异操作[42]来避免多样性丢失.设权重数组变异概率为Pm,在(0,1) 之间随机生成rndi,如果rndi<Pm,则随机选择该量子态粒子上[n/2]个量子比特,通过公式(10) 进行变异操作.

$\left[ \begin{matrix} 0 & 1 \\ 0 & 1 \\ \end{matrix} \right]\left[ \begin{matrix} \cos ({{\theta }_{ij}}) \\ \sin ({{\theta }_{ij}}) \\ \end{matrix} \right]=\left[ \begin{matrix} \sin ({{\theta }_{ij}}) \\ \cos ({{\theta }_{ij}}) \\ \end{matrix} \right]=\left[ \begin{matrix} \cos \left( \frac{\pi }{2}-{{\theta }_{ij}} \right) \\ \sin \left( \frac{\pi }{2}-{{\theta }_{ij}} \right) \\ \end{matrix} \right]$ (10)

设有m个量子态粒子共经历了gmax次迭代优化.Pil对应的权重数组Wil,为粒子i当前搜索到的适应度值最高的权重数组.Pg对应的权重数组为Wg,为整个粒子群当前搜索到的适应度值最大的权重数组.

OWA具体实现如下:

算法 1. OWA.

输入:社会网络数据集.

1. 选定衡量指标.

2. 确定最佳混合指标的单位指标.

3. 通过公式(3) 初始化,生成m个携带权重数组的量子态粒子.

4. For g=1 to gmax:

For i=1 to m:

5. 量子态粒子概率幅PicPis通过公式(7) 和公式(8) 对应的权重数组WisWic.

If fitness(MixSimIndex(Wic))>fitness(MixSimIndex(Wil)) then Pil=Pic End

If fitness(MixSimIndex(Wis))>fitness(MixSimIndex(Wil)) then Pil=Pis End

If fitness(MixSimIndex(Wil))>fitness(MixSimIndex(Wg)) then Pg=Pil End

6. 通过公式(9) 更新权重数组,${{P}_{is}}={{\bar{P}}_{is}},{{P}_{ic}}={{\bar{P}}_{ic}}$.

7. 通过公式(10) 对权重数组进行变异处理.

End

End

8. Pg通过公式(7) 或者公式(8) 转换为对应的权重数组,确定最佳混合指标并输出.

算法OWA可以自动计算各单位指标的合适权重,快速、高效地确定最佳的混合指标,避免了考虑单位指标数量级的差异.对于本文采用的衡量指标AUC,最佳混合指标的单位指标只需满足AUC值大于0.5.当有多个相似性指标都满足单位指标的要求时,可以把所有满足条件的指标都作为MixSimIndex的单位指标.在OWA迭代足够多次数的情况下,不利于AUC值提升的单位指标的权重会被确定为0.但实际操作中,可适当选取一定数目满足条件的相似性指标作为单位指标,比如,简单选取AUC值最大的两个相似性指标,时间复杂度可由O(nxmx gmax)降低到O(2xmxgmax),这会有效地提升OWA的效率.

为了更好地解释算法OWA,我们继续探讨表 2中构造的WS小世界网络.如果n=2,仅仅选定PA和CN两个指标作为MixSimIndex单位指标,设其对应的权重分别为w1,w2.设量子粒子群规模为150,通过OWA算法在200次迭代后,可得到w1=0.97,w2=0.03.此时的AUC值可高达0.708 5,远高于独立的相似性指标(表 3)和没有优化的一般混合权重指标(见表 4).同时,如表 5所示,在相同的实验设置下,基本的PSO[40]得到的最佳混合指标AUC值为0.691 2,低于OWA的表现,也证明了OWA的高效性.

Table 5 Algorithm OWA and basic PSO efficiency correspondenc 表 5 算法OWA和基本的PSO效率对应

2.2 算法 FDA

第2.2.1节在BA无标度网络实例上验证了链路预测衡量指标值变动与网络演化波动的一致性.第2.2.2节详细介绍了算法FDA,利用链路预测衡量指标量化不同时刻的网络演化波动,发现异常波动,进行事件检测.同时,在第2.2.1节和第2.2.2节中,我们都会结合BA无标度网络进行详细解释.

2.2.1 一致性分析

给定的网络Gt时刻的网络快照可用gt表示,假设现有网络Gn个快照构成集合{g1,g2,…,gt,…,gn},每两个相邻快照之间的时间间隔是一致的.第2.1节中的OWA已能在给定网络快照的情况下,高效确定当前时段的最佳混合指标.基于最佳混合指标的链路预测算法,能够取得最好的链路预测效果(最高的衡量指标值).因为网络演化机制与链路预测算法具有内在的一致性[35, 43],所以基于最佳混合指标的链路预测算法最符合当前网络的演化机制.正常情况下,当前网络的演化机制会在一段时间内保持一定程度的稳定性,所以基于当前最佳混合指标的链路预测算法会在一段时间内取得较高的衡量指标值.当某时刻最佳混合指标的衡量指标值发生了显著的下降,可以猜测发生了网络事件,扰乱了网络的内在演化机制,造成衡量指标值的下降.

比如,基于网络快照gt得到t时刻的最佳混合指标,表示为BMixSimIndext.如果没有网络事件发生,那么基于BmixSimIndext的链路预测算法应该在后续的t+1和t+2时刻对应的网络快照gt+1,gt+2上仍然取得较高的AUC值.如果基于BMixSimIndext的链路预测算法在网络快照gt+1上保持着较高的AUC值,在网络快照gt+2上AUC值明显下降,那么可以推测t+1到t+2时段发生了网络事件,扰乱了网络内在的演化机制,导致BMixSimIndext不再符合t+1到t+2时段的网络演化机制,所以基于BMixSimIndext的链路预测算法不能在网络快照gt+2取得较高的AUC值.

Barabási等人基于优先连接的网络演化机制提出了著名的BA无标度模型[4].为了更好地解释链路预测衡量指标变动与网络演化波动的一致性,我们构建BA网络实例N1和加入事件的BA网络实例N2.N1构造步骤如下:(1) 初始网络为空,第1个时间步加入一个节点;(2) 从第2个时间步开始,每次加入1个新节点,并且每个新节点优先与现有的度最大的节点构成一条边;(3) 迭代200个时间步后停止.N2构造步骤如下:

(1) 正常网络演化阶段:第1个时间步加入一个节点.从第2个时间步开始,每次加入1个新节点,并且每个新节点优先与现有的度最大的节点构成一条边.迭代120个时间步后停止.

(2) 网络事件发生阶段:从第121时间步开始到第159时间步,每次加入1个新节点,并且每个新节点随机的与现有节点构成一条边.

(3) 网络演化恢复正常阶段:从第160时间步开始到第200时间步,每次加入1个新节点,每个新节点再次优先与现有的度最大的节点构成一条边.

网络N1和N2的区别在于,N2从第121时间步到第159时间步中采用了不同于N1的演化机制来模仿网络事件的发生.AUCt表示基于t时刻的网络快照gt进行链路预测得到的AUC值.

$AUC=\frac{{n}'+0.5{n}''}{n}$

t时刻网络快照gt相对于t-1时刻网络快照gt-1新增加的边构成测试边集合,t时刻节点之间不存在的边构成不存在边集合.

为了检测出从第121时间步到第159时间步发生的网络事件,对网络N1和N2作如下探究:

(1) 在正常网络演化阶段第120时间步结束时,N1和N2的网络快照一样,其各相似性指标的AUC120值相同,见表 6.

Table 6 Common similarity index AUC120 表 6 常见相似性指标AUC120

表 6中,所有相似性指标中只有PA的AUC值超过0.5,所以只能选取PA作为最佳混合指标的单位指标,则PA的权重一定为1,第120时间步结束时当前网络的最佳混合指标BMixSimIndex120=PA.

(2) 每隔20个时间步,利用衡量指标AUC评价基于BMixSimIndex120=PA表 1中各相似性指标的链路预测算法效果,其AUC值如图 3所示.由于SA,JA,SO,HPI,LNH与CN,AA有相似的曲线,为了让图 3更清晰,只有CN,AA指标被选取展示.PA在无事件发生的网络N1和发生事件的网络N2上的变化都在图 3中进行了展示.

Fig. 3 Similarity index corresponding to the index value of the time step change map 图 3 相似性指标对应的衡量指标值随时间步变化图

图 3可得出如下结论:

(1) 当选取正确的相似性指标(AUC值大于0.5) 时,链路预测衡量指标变动与网络演化波动的具有一致性.对于上述N2网络的例子,PA(BMixSimIndex120)可以很好地通过其AUC值变动来反映网络演化波动.但是SA,JA,SO,HPI,LNH,CN和AA一直没有太大的变化,无法反映网络演化波动.PA指标对应的AUC值在正常网络演化阶段(第1时间步~第120时间步)一直高于0.7,但是在网络事件发生阶段(第121时间步~第159时间步),由于网络内在演化机制发生了改变(每个新节点优先与现有的度最大的节点构成一条边变成每个新节点随机的与现有节点构成一条边),PA对应的AUC值迅速下降,远低于0.7.在网络演化恢复正常阶段(第160时间步~第200时间步),PA对应的AUC值才逐渐提升.对于没有事件发生的N2而言,它的最佳混合指标BMixSimIndex120=PA的衡量指标值一直保持高于0.7.

(2) 通过最佳混合指标对应的衡量指标,可以很好地进行网络事件检测.

基于最佳混合指标BMixSimIndex120=PA,可以很好地反映N2的网络事件发生阶段和正常网络演化阶段的差异.

2.2.2 FDA的实现

第2.2.1节验证了链路预测衡量指标变动与网络演化波动的一致性.本节进一步提出了算法FDA,以有效地避免非事件引起的网络正常波动带来的干扰,发现事件引起的异常网络波动,进行事件检测.假设现有网络快照集{g1,g2,…,gt,…,gn},Mt代表t时刻的网络演化波动的评价值,用公式(11) 表示:

${{M}^{t}}=\left\{ \begin{array}{*{35}{l}} AU{{C}^{t}}-\frac{\sum\limits_{T=t-\text{ }\!\!\Delta\!\!\text{ }t}^{t-1}{AU{{C}^{T-1}}}}{\text{ }\!\!\Delta\!\!\text{ }t},\text{ }0<\text{ }\!\!\Delta\!\!\text{ }t<t,\text{ }\!\!\Delta\!\!\text{ }t为整数 \\ AU{{C}^{t}},\text{ }\!\!\Delta\!\!\text{ }t=0 \\ \end{array} \right.$ (11)

其中,Δt表示记忆时间.t时刻的网络演化波动值Mt是由AUCtAUCt-1AUCtt平均值的差值的决定.当多个事件引起连续的网络波动时,Δt应设置较小值来避免事件间的相互干扰.当Δt=0时,此时Mt=AUCt,相当于t时刻网络演化波动的评价值直接由t时刻链路预测的AUC值来表示.

MD为事件检测阈值,可以根据需求来灵活设置.当Mt>MD时,则认为t时刻的网络演化发生了显著异常波动,很可能发生了事件.设置放大系数A,通过公式(12) 对网络演化波动序列(M1,M2,…,Mt,…,Mn)中的异常波动进行放大处理,得到事件检测序列(F1,F2,…,Ft,…,FT).Ft是通过对Mt放大处理后得到的t时刻的网络事件检测值.Ft可以为负数值,值越小,表明此时的网络演化波动越大,发生事件的可能性就越大.事件检测序列(F1,F2,…,Ft,…,FT)相对于网络演化波动序列(M1,M2,…,Mt,…,MT),可以更好地区分非事件引起的网络正常波动和事件引起的异常波动.

${{F}^{t}}=\left\{ \begin{array}{*{35}{l}} A\times {{M}^{t}},\text{ }{{M}^{t}}<MD \\ {{M}^{t}},\text{ }{{M}^{t}}\ge MD \\ \end{array} \right.$ (12)

定义时刻TO为网络检测稳定点,一般可选取前后网络演化没有明显波动的时刻作为TO.事件检测阈值MD,网络检测稳定点TO,放大系数A可人为设置,增强了算法的灵活性.一种基于AUC的算法FDA表示如下:

算法 2. 基于AUC的FDA.

输入:事件检测阈值MD,网络检测稳定点TO,放大系数A,记忆时间Δt,网络快照集合{g1,g2,…,gt,…,gn}.

1. 从网络演化稳定的时刻中选取TO.

2. 基于TO时的网络快照,通过算法OWA得到TO时最佳混合指标BMixSimIndexTO.

3. For t=1 to n

执行公式(14) ,得到Mt.

执行公式(15) ,得到Ft.

End

4. 输出事件检测序列(F1,F2,…,Ft,…,FT).

公式(11) 是基于衡量指标AUC提出的,但衡量指标AUC只是宏观上评价整体网络演化波动,并未考虑微观上每个节点演化的差异.实际上,如果节点周围的拓扑结构变化符合网络演化规律,则可以看做是正常演化,其对网络演化波动影响较小.如果节点周围拓扑结构变化不符合演化规律,则极有可能是事件发生导致内在演化规律被打破.考虑节点的微观演化,有助于更精准、全面地量化网络演化波动,进一步避免非事件引起的网络正常波动的干扰.于是,我们进一步提出一种考虑了节点微观演化的衡量指标mAUC,对宏观的AUC值进行调整.

将链路预测衡量指标$AUC=\frac{{n}'+0.5{n}''}{n}$引入到微观节点层面得到$AUC_{i}^{t}$,求解$AUC_{i}^{t}$时,把t时刻节点i与其他节点相对于t-1时刻新增的连边作为测试集合,节点it时刻网络中其他节点之间不存在的连边构成不存在边集合.G(t)表示t时刻网络节点集合,Nt表示G(t)中的节点数目.

用公式(13) 和公式(14) 表示如下:

$mAU{{C}^{t}}=\left( \frac{\sum\limits_{i\in \Gamma (T)}{AUC_{i}^{t}}}{{{N}_{t}}} \right)\times AU{{C}^{t}}$ (13)
${{M}^{t}}=\left\{ \begin{array}{*{35}{l}} mAU{{C}^{t}}-\frac{\sum\limits_{T=t-\text{ }\!\!\Delta\!\!\text{ }t}^{t-1}{mAU{{C}^{T-1}}}}{\text{ }\!\!\Delta\!\!\text{ }t},\text{ }0<\text{ }\!\!\Delta\!\!\text{ }t<t,\text{ }\!\!\Delta\!\!\text{ }t \\ mAU{{C}^{t}},\text{ }\!\!\Delta\!\!\text{ }t=0 \\ \end{array} \right.为整数$ (14)

算法 3. 基于mAUC的FDA.

输入:事件检测阈值MD,网络检测稳定点TO,放大系数A,记忆时间Δt,网络快照集合{g1,g2,…,gt,…,gn}.

1. 基于TO时的网络快照,通过算法OWA得到TO时最佳混合指标BMixSimIndexTO.

2. For t=1 to n

执行公式(16) 和公式(17) ,得到Mt.

执行公式(15) ,得到Ft.

End

3. 输出事件检测序列(F1,F2,…,Ft,…,FT),较小F值对应的时刻即为潜在事件发生点.

为了更好地解释算法FDA,我们继续用第2.2.1节中N2的例子进行说明.设置MD=-0.1,TO=120,A=10,Δt=1,分别基于AUC和mAUC的FDA,得到的事件检测序列如图 4所示.

Fig. 4 Network N2 event detection sequence change map 图 4 网络N2上的事件检测序列变化图

图 4可以得出如下结论:

(1) 基于AUC和mAUC的FDA都可以很好地检测出网络事件.在网络事件发生阶段(第121时间步~第159时间步),网络事件检测值都大幅度降低.正常网络演化阶段(第40时间步~第120时间步)和网络演化恢复正常阶段(第160时间步~第200个时间步),网络事件检测值一直相对较高.同时,经过FDA的处理,网络事件检测值比衡量指标本身(如图 3所示)具有更显著的事件检测效果.

(2) 基于mAUC的FDA通过考虑节点的微观演化对宏观衡量指标AUC值进行纠正,能够更真实地反映网络演化的波动,有效避免非事件造成的AUC值变动.从第40时间步~第80时间步,网络N2正在构建中,还没有达到稳定状态,但是微观上,每个节点是符合网络的内在演化机制,所以基于mAUC的FDA仍能保持相对较高的网络事件检测值,很好地避免了非事件引起的正常网络波动的干扰.

3 实验分析

本节通过实验来验证IndexEvent方法中的关键理论.第3.1节介绍了实验中使用的真实的社会网络数据集. 第3.2节利用OWA确定各真实数据集上的最佳混合指标,并与表 1中提到的常见相似性指标对比来表明混合指标的有效性.基于第3.2节得出的最佳混合指标,第3.3节通过FDA量化各数据集上的不同时段的网络演化波动,进行事件检测.并通过与真实的事件进行比较,证明了IndexEvent方法的准确性.

3.1 数据集描述

为了验证本文提出的IndexEvent方法的有效性,通信网络(VAST)和邮件网络(Enron)被用作实验数据集. VAST数据集源自IEEE VAST 2008[44],包含400人在10天内的通话数据网络,并且已知在第7天与第8天之间发生了一次高层变动,引起了网络波动.Enron数据集源自Enron公司的内部邮件联系网络[42],包含150人在111周内的通信数据,本节选择代表性的连续的40周,期间包括公司被收购、破产等多个事件.VAST数据集的特点是发生的事件单一,事件发生的时间和原因确定,有助于检测特定事件,并分析事件前后网络的变化情况. Enron数据集的特点是多个事件相继发生,有利于我们分析多个事件对网络的连续影响,分析不同事件所起的作用.

3.2 最佳混合指标确定

通过在真实网络VAST和Enron的仿真实验,本节验证混合指标的在真实网络应用中的可行性和算法OWA确定最佳混合指标的高效性.

· 对于VAST真实通话网络

(1) 以所选10天里的第1天作为基准时刻TO,TO时刻基于表 1的8种不同相似性指标的链路预测算法的AUC值见表 7.

Table 7 AUC value of the link prediction algorithm with different similarity indexes for VAST dataset at TO time 表 7 TO时刻,VAST数据集上,不同相似性指标链路预测算法的AUC值

(2) 基于表 7所示结果,选取AUC值靠前的PA和AA作为混合指标的单位指标,利用OWA算法确定PA和AA对应的权重,可得其最佳混合指标BMixSimIndex1=0.273PA+0.727AA.在TO时刻,其对应的AUC值为0.516 13,略高于基于它的单位指标PA和AA各自对应的链路预测精度;同时远高于表 1的8种其他相似性指标的链路预测精度.

(3) 由于SA,JA,SO,HPI,LNH,CN和AA有相似的曲线,所以为了让图 5更清晰,只有PA,AA指标被选取展示.BMixSimIndex1和PA可以比其他相似性指标更好地反映网络在第7天与第8天之间发生的高层变动事件.

Fig. 5 Change of AUC values of BMixSimIndex1,PA,AA with the number of days in VAST network 图 5 在VAST网络中,BMixSimIndex1,PA,AA的AUC值随天数的变化趋势

· 对于Enron真实通信网络

(1) 以所选40周里的第2周作为基准时刻TO,不同相似性指标的链路预测算法的AUC2值见表 8.

Table 8 AUC2 value of the link prediction algorithm with different similarity indexes for Enron dataset at TO time 表 8 TO时刻,Enron数据集上,不同相似性指标链路预测算法的AUC2

(2) 基于表 8所示结果,选取AUC值靠前的PA和CN作为单位指标,利用算法OWA确定PA和CN对应的权重,可得其最佳混合指标为BMixSimIndex2=0.014PA+0.986CN.在TO时刻,其对应的AUC值为0.638 75远高于8种独立相似性指标的链路预测算法精度.

综述,通过分别在VAST和Enron上进行混合指标的讨论,证明了混合指标在真实网络中的可行性和OWA的有效性.

(1) 当最佳混合指标中出现某个单位指标权重为1、其他指标权重均为0的特例情况时,此时该网络最佳混合指标和这个权重为1的独立相似性指标的链路预测度精度一样.其他情况下的网络均可通过OWA找到一个链路预测精度优于独立相似性指标的最佳混合指标.

(2) 真实网络的演化机制越复杂,通过OWA得到最佳混合指标的优势越明显.因为独立指标很难反映多种演化机制混合的真实网络,而混合指标则能更全面地反映.在Enron真实网络中,多个事件连续发生,网络的内在机制发生了重大变化,该网络对应的最佳混合指标精度比表现最佳的独立指标PA高0.13.而在单个事件发生的VAST中,网络的演化机制变化较小,链路预测的精度仅仅提高了0.001 2.

3.3 事件检测分析

通过在真实网络VAST和Enron上实验,本节验证了链路预测衡量指标值变动与网络演化波动的一致性关系,并验证了FDA进行事件检测的准确性.

对VAST通话数据集,设置MD=-0.02,TO=1,A=10,Δt=1,VAST上的事件检测序列如图 6所示,可得如下结论:

Fig. 6 Sequence of event detection on VAST 图 6 VAST上的事件检测序列图

(1) VAST通话网络在第7天与第8天之间发生了一次高层变动,基于AUC和基于mAUC的FDA都能显著地检测到这次事件的发生,第6天到第7天的事件检测值大幅度下降.当到了第8天时,事件检测值恢复到正常水平,高层变动产生的影响慢慢减弱.

(2) 基于AUC的FDA对网络演化波动更加敏感,在高层变动事件发生第7天,事件检测值大幅度降低,在第2天和第3天也出现了一定的波动.基于mAUC的FDA有效地避免了基于AUC的FDA在第2天和第3天产生的非事件引起的网络波动干扰,能够精准地检测出第7天事件发生引起的网络波动.

对于Enron通信数据集,设置MD=0,TO=1,A=1,Δt=0,Enron上的事件检测序列如图 7所示,表 9列出了Enron网络检测出的事件与真实事件对应关系.可得如下结论:

Fig. 7 Event detection sequence on Enron 图 7 Enron上的事件检测序列

Table 9 Corresponding relationship between the event and the real event detected by the Enron network 表 9 Enron网络检测出的事件与真实事件对应关系

(1) Enron网络中多个事件连续发生,基于AUC和基于mAUC的FDA都很好地检测出多个网络事件.在网络事件发生时,事件检测值都会降低.

(2) 基于AUC的FDA对网络演化波动更加敏感,连续事件发生时,事件检测值变动较大,并且在没有发生事件是也会有一定波动.基于mAUC的FDA只在事件发生时才出现事件检测值降低,避免了正常波动带来的干扰.同时,可判断事件2(美国证券交易委员会要求提交交易内容)严重扰乱了网络内在演化机制,引起了较大的网络演化波动,导致事件检测值迅速下降.

综上,通过对VAST和Enron真实网络上事件检测分析,证明了基于AUC和基于mAUC的FDA在单个事件发生的网络和多个事件发生的网络上都能进行有效的事件检测,并且可以对不同事件对网络的影响进行定量评估.基于AUC的FDA对网络波动更加敏感,容易受到非事件引起的网络波动的干扰.基于mAUC的FDA由于考虑了节点的微观演化,能够更精准地检测出事件引起的波动,避免无效波动的干扰.

4 结论及展望

为了检测网络事件,量化事件对社会网络演化产生的影响,本文提出了一种混合指标群智能方法IndexEvent:利用最佳权重算法OWA来确定当前时段网络的最佳混合指标;然后,通过基于AUC或基于mAUC的网络波动检测算法FDA检测事件.为了验证IndexEvent方法的有效性,本文基于WS小世界网、BA无标度网络、VAST和Enron真实网络进行了大量实验探讨,并得出以下结论:

(1) 对于特定真实网络,在最佳混合指标为某个单位指标权重为1、其他指标权重均为0的特殊情况下,最佳混合指标和这个权重为1的独立相似性指标的链路预测度精度一样.其他情况均可以通过OWA找到一个链路预测精度优于独立相似性指标的混合指标;并且,真实网络的演化机制越复杂,通过OWA得到最佳混合指标的优势越明显.

(2) 基于AUC的FDA对网络演化波动更加敏感,非事件引起的正常网络波动容易对事件检测结果造成干扰.基于mAUC的FDA由于考虑了节点的微观演化,能够更好地避免正常网络波动的干扰,精准地检测出事件引起的网络异常波动.

(3) 无论是在WS小世界网络和BA无标度网络的实例,还是在VAST和Enron的真实网络,IndexEvent方法检测出的事件与真实事件有很好的匹配关系,证明了IndexEvent的准确性高,具有很好的实用性.

进一步的研究仍然需要在以下两个方面继续:

(1) 尝试利用链路预测去确定真实网络中不同的网络演化机制所占的具体比重;

(2) 进一步探讨各种相似性指标及最大似然估计指标之间的关系.

致谢 我们真诚地向对本文的工作给予支持和建议的审稿人、主编、编辑、同行、老师和同学表示感谢.
参考文献
[1] Reuter T, Bielefeld U, Papadopoulos S, Petkos G, Vries CD, Mezaris V. Social event detection at mediaeval 2013:Challenges, datasets, and evaluation. In:Proc. of the MediaEval Workshop. 2013. 18-19.
[2] Hidalgo CA, Rodriguez-Sickert C. The dynamics of a mobile phone network. Physica A Statistical Mechanics & Its Applications, 2008, 387 (12) :3017–3024. [doi:10.1016/j.physa.2008.01.073]
[3] Watts DJ, Strogatz SH. Collective dynamics of "small-world" networks. Nature, 1998, 393 (6684) :440–442. [doi:10.1038/30918]
[4] Zhang Z, Wu B. Pfaffian orientations and perfect matchings of scale-free networks. Theoretical Computer Science, 2015, 570 (C) :55–69. [doi:10.1016/j.tcs.2014.12.024]
[5] Washio T, Motoda H. State of the art of graph-based data mining. AcmSigkdd Explorations Newsletter Homepage, 2003, 15 (1) :59–68. [doi:10.1145/959242.959249]
[6] Papadimitriou P, Dasdan A, Garcia-Molina H. Web graph similarity for anomaly detection. Journal of Internet Services & Applications, 2010, 1 (1) :19–30. [doi:10.1007/s13174-010-0003-x]
[7] Mcculloh IA, Carley KM, Mcculloh IA, Carley KM. Social network change detection. Technical Report, CMU-ISR-08-116, Institute for Software Research, School of Computer Science, Carnegie Mellon University, 2008.[doi:10.2139/ssrn.2726799]
[8] Wan X, Milios E, Kalyaniwalla N, Janssen J. Link-Based event detection in email communication networks. In:Proc. of the SAC ACM Symp. on Applied Computing. 2009.[doi:10.1145/1529282.1529618]
[9] Taskar B, Abbeel P, Koller D. Discriminative probabilistic models for relational data. Eprint Arxiv, 2012. 485-492.
[10] Aaron C, Cristopher M, Newman MEJ. Hierarchical structure and the prediction of missing links in networks. Nature, 2008, 453 (7191) :98–101. [doi:10.1038/nature06830]
[11] Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 2007, 58 (7) :1019–1031. [doi:10.1002/asi.20591]
[12] Kossinets G, Watts DJ. Reports empirical analysis of an evolving social network. Science, 2006, 311 (5757) :88–90. [doi:10.1126/science.1116869]
[13] Sarukkai RR. Link prediction and path analysis using Markov chains. Computer Networks, 2000, 33 (1) :377–386. [doi:10.1016/S1389-1286(00)00044-X]
[14] Zhu J, Hong J, Hughes JG. Using Markov chains for link prediction in adaptive Web sites. In:Proc. of the ACMSigWeb Hypertext. 2002. 60-73.
[15] Clauset A, Moore C, Newman MEJ. Hierarchical structure and the prediction of missing links in networks. Nature, 2008, 453 (7191) :98–101. [doi:10.1038/nature06830]
[16] Guimera R, Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks. Proc. of the National Academy of Sciences, 2010,106(52):22073-22078.[doi:10.1073/pnas.0908366106]
[17] Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the American Society for Information Science & Technology, 2007, 58 (7) :1019–1031. [doi:10.1002/asi.20591]
[18] Rapoport A. Spread of information through a population with socio-structural bias:I. Assumption of transitivity. The Bulletin of Mathematical Biophysics, 1953, 15 (4) :523–533. [doi:10.1007/BF02476440]
[19] Jaccard P. Etude Comparative de la distribution florale dans une portion des Alpes et du Jura. Bulletin de La Societe Vaudoise Des Sciences Naturelles, 1990, 37 (142) :547–579. https://www.amazon.com/Etude-comparative-distribution-florale-portion/dp/B005WVYTTK
[20] Adamic LA, Adar E. Friends and neighbors on the Web. Social Networks, 2003, 25 (3) :211–230. [doi:10.1016/S0378-8733(03)00009-1]
[21] Barabasi AAR. Emergence of scaling in random networks. Science, 1999, 286 (5439) :509–512. [doi:10.1126/science.286.5439.509]
[22] Lichtenwalter RN, Lussier JT, Chawla NV. New perspectives and methods in link prediction. In:Proc. of the ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Washington, 2010. 243-252.[doi:10.1145/1835804.1835837]
[23] Symeonidis P, Iakovidou N, Mantas N, Manolopoulos Y. From biological to social networks:Link prediction based on multi-way spectral clustering. Data and Knowledge Engineering, 2013, 87 (4) :226–242. [doi:10.1016/j.datak.2013.05.008]
[24] Huang Z, Li X, Chen H. Link prediction approach to collaborative filtering. In:Proc. of the Joint Conf. on Digital Libraries. ACM Press, 2005. 7-11.[doi:10.1145/1065385.1065415]
[25] Rao J, Wu B, Dong YX. Parallel link prediction in complex network using MapReduce. Ruan Jian Xue Bao/Journal of Software, 2012, 23 (12) :3175–3186(in Chinese with English abstract). [doi:10.3724/SP.J.1001.2012.04206] http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4206&journal_id=jos
[26] Salton G, McGill MH. Introduction to Modern Information Retrieval. New York:McGraw-H Hill, 1983.
[27] Sørensen T. A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons. Biol Skr, 1948, 5 :1–34. https://www.amazon.co.uk/establishing-Similarity-application-vegetation-Videnskabernes/dp/B0017ZDFV8
[28] Ravasz E, Somera AL, Mongru DA, Oltvai ZN, Barabási AL. Hierarchical organization of modularity in metabolic networks. Science, 2002, 297 (5586) :1551–1555. [doi:10.1126/science.1073374]
[29] Leicht EA, Holme P, Newman MEJ. Vertex similarity in networks. Physical Review E, 2006, 73 (2) :026120. [doi:10.1103/PhysRevE.73.026120]
[30] Noble CC, Cook DJ. Graph-Based Anomaly Detection. In:Proc. of the ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Washington, 2003. 631-636.[doi:10.1145/956750.956831]
[31] Priebe CE, Conroy JM, Marchette DJ. Scan statistics on enron graphs. Computational & Mathematical Organization Theory, 2005, 11 (3) :229–247. [doi:10.1007/s10588-005-5378-z]
[32] Wu B, Wang B, Yang SQ. Framework for tracking the event-based evolution in social networks. Ruan Jian Xue Bao/Journal of Software, 2011, 22 (7) :1488–1502(in Chinese with English abstract). [doi:10.3724/SP.J.1001.2011.03841] http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=3841&journal_id=jos
[33] Baruah RD, Angelov P. Evolving social network analysis:A case study on mobile phone data. In:Proc. of the 2012 IEEE Conf. on Evolving and Adaptive Intelligent Systems (EAIS). IEEE, 2012. 114-120.[doi:10.1109/EAIS.2012.6232815]
[34] Qiao SJ, Tang CJ, Peng J, Liu W, Wen FL, Qiu JT. Mining key members of crime networks based on personality trait simulation email analysis system. Chinese Journal of Computer, 2008, 31 (10) :1795–1803(in Chinese with English abstract). [doi:10.3321/j.issn:0254-4164.2008.10.014]
[35] Kashima H, Abe N. A parameterized probabilistic model of network evolution for supervised link prediction. Trans. of the Japanese Society for Artificial Intelligence, 2006, 22 (2) :340–349. [doi:10.1109/ICDM.2006.8]
[36] Hanley JA, Mcneil BJ. The meaning and use of the area under a receiver operating chracteristic (roc) curve. Radiology, 1982, 143 (1) :29–36. [doi:10.1148/radiology.143.1.7063747]
[37] Herlocker JL, Konstan JA, Terveen LG, Riedl JT. Evaluating collaborative filtering recommender systems. ACM Trans. on Information Systems, 2004, 22 (1) :5–53. [doi:10.1145/963770.963772]
[38] Zhou T, Ren J, Medo M, Zhang YC. Bipartite network projection and personal recommendation. Physical Review E (Statistical Nonlinear and Soft Matter Physics), 2007, 76 (4) :70–80. http://cn.bing.com/academic/profile?id=2098152575&encoded=0&v=paper_preview&mkt=zh-cn
[39] Bouwmeester D, Ekert A, Zeilinger A. The physics of quantum information. In:Proc. of the Quantum Cryptography Quantum Teleportation Quantum Computation. 2010.
[40] Tang D, Cai Y, Zhao J, Xue Y. A quantum-behaved particle swarm optimization with memetic algorithm and memory for continuous non-linear large scale problems. Information Sciences, 2014, 289 (24) :162–189. [doi:10.1016/j.ins.2014.08.030]
[41] Schutte JF, Groenwold A. A study of global optimization using particle swarms. Journal of Global Optimization, 2004, 31 (31) :93–108. [doi:10.1007/s10898-003-6454-x]
[42] http://www.cs.cmu.edu/~enron/2012/8/1
[43] Liu HK, Lü LY, Zhou T. Uncovering the network evolution mechanism by link prediction. Scientia Sinica PhysMechAstron, 2011, 41 (7) :816–823(in Chinese with English abstract). [doi:10.1360/132010-922]
[44] http://www.cs.umd.edu/hcil/VASTchallenge08/2012/10/8
[25] 饶君, 吴斌, 东昱晓. MapReduce环境下的并行复杂网络链路预测. 软件学报, 2012,23 (12) :3175–3186. [doi:10.3724/SP.J.1001.2012.04206] http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4206&journal_id=jos
[32] 吴斌, 王柏, 杨胜琦. 基于事件的社会网络演化分析框架. 软件学报, 2011,22 (7) :1488–1502. [doi:10.3724/SP.J.1001.2011.03841] http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=3841&journal_id=jos
[34] 乔少杰, 唐常杰, 彭京, 等. 基于个性特征仿真邮件分析系统挖掘犯罪网络核心. 计算机学报, 2008,31 (10) :1795–1803. [doi:10.3321/j.issn:0254-4164.2008.10.014]
[43] 刘宏鲲, 吕琳媛, 周涛. 利用链路预测推断网络演化机制. 中国科学:物理学力学天文学, 2011,41 (7) :816–823. [doi:10.1360/132010-922]