基于社团结构的加权社会网络最短路径算法

可在www.sciencedirect.com在线获取ScienceDirectCAAITransactions on Intelligence Technology 1（2016）114e123http://www.journals.elsevier.com/caai-transactions-on-intelligence-technology/原创文章基于社团结构的社交网络最短路径算法龚茂国a，*，李冠军a，王赵a，马丽佳a，田大勇b西安电子科技大学智能感知与图像理解教育部重点实验室，智能感知与计算国际研究中心，西安7100712007年，澳大利亚新南威尔士州百老汇悉尼科技大学量子计算和智能系统中心2016年6月2日在线发布摘要在大规模网络分析中，寻找任意两个节点之间的最短路径（SP）是一项艰巨但意义重大的任务。SP算法可以帮助我们分析加权社会网络中的信息传播性能，研究加权社会网络中的潜在关系等，但是随着社会网络规模的增大，传统的SP算法的性能越来越差，目前还没有一种适合加权社会网络的算法。网络分析的一些特点有利于解决这一问题，而传统方法所忽略的社区结构就是其中最重要的特点之一。本文将社区检测算法与传统的搜索方法相结合，提出了一种基于社区检测的最短路径算法。SPCD利用社区结构构造社区图，缩小搜索范围。该算法提高了时间效率，并保持了精度规模的SP。五个真实世界的网络上的实验结果表明，所提出的方法的有效性SP问题。Copyright© 2016 ， 重 庆 理 工 大 学 . Elsevier B. V. 制 作 和 托 管 这 是 CC BY-NC-ND 许 可 证 下 的 开 放 获 取 文 章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：最短路径;社区结构;加权社会网络1. 介绍近年来，社会网络的研究引起了社会学、信息学和计算机科学的广泛关注[1，2]。社会网络是由一组社会行动者（如个人或组织）和这些行动者之间的一组二元关系组成的社会结构。大量的数据和资源使得分析社交网络相关问题变得至关重要。社会学在社会影响、社会关系、社会*这项工作得到了国家自然科学基金61273317和61422209、国家青年拔尖人才培养计划和高等教育博士点专项研究基金20130203110011的部分支持。*通讯作者。电子邮件地址：gong@ieee.org（M. Gong）。同行评议由重庆理工大学负责。社会群体、不平等、疾病传播和信息交流[3]。计算社会网络中节点之间距离或关系的SP问题是社会网络分析中一个极其重要的问题。它可以用来研究信息的传播行为，特别是最快的信息传播行为.推荐系统也是基于SP问题的。例如，在分析科学家之间的关系时，利用SP问题建立和分析了科学家的合作网络。通过对科学家合作网络的分析，可以提高工作效率和审稿效率. SP问题是分析网络结构的一个基本方面，如介数、平均距离等。随着网络规模的增大，以往的算法可能不适合现有的网络，因此需要针对大规模网络的有效方法。本文主要研究加权社会网络中任意两个节点之间的SP问题。SP问题涉及从一个节点找到最短路径http://dx.doi.org/10.1016/j.trit.2016.03.0112468-2322/Copyright© 2016，重庆理工大学由爱思唯尔公司制作和主持这是一篇基于CC BY-NC- ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。M. Gong等人/CAAI Transactions on Intelligence Technology 1（2016）114e 123115¼¼----J J¼在给定的网络中，将特定的起点到指定的目的地，同时最小化与路径相关的总成本。在图中，找到从源节点s到目的节点d的最小成本路径被称为点对点（P2P）问题，但常见的变体将单个节点固定为源节点，并找到从源到图中所有其他节点的最短路径。除了P2P问题外，其他的最短路径问题，如单目的地、全对等，都可以转化为单源最短路径问题，其中弧长非负的单源最短路径问题得到了最广泛的研究[4]。对于一般的网络，传统的Dijkstra算法可用于求解所有的非负的、加权或非加权的网络，而不需要任何特定领域的信息。虽然它是一个单源的算法，我们可以把它转化为一个P2P算法，在目的节点终止。但是它的时间复杂度很高，为O（n2），因此在社交网络中，特别是大规模社交网络中，它可能不能很好地应用于SP。改进的标准宽度优先算法的时间复杂度为O（n），但它适用于非加权网络[5]。随着网络规模的增大，研究者们开始利用网络的特定领域信息来处理它，在交通网络中，研究者们采 用自 然 层次 结 构 来显 著 提高 最 短路 径 算法 的 速 度[6e10]，[11]中给出了更多的算法。显然，这些算法不能应用于社会网络。从交通网络的角度来看，社会网络的特性也可以应用到SP问题中。社区性是社会网络的重要特征之一。近年来，社区检测已经取得了很大的进展，在网络分析领域的关注。社区结构类似于小世界效应和右偏度分布，这是复杂网络中的一个重要特性[12]。定性地说，社区被定义为图的一个子集，其中节点的互连比网络的其余部分更密集[13，14]。对于一般情况下的赋权图，许多研究主要集中在各种准则上，包括模度[15]、结构密度[16]和划分密度[17]。Blondel等人引入了一种快速贪婪方法（BGLL）来优化模块化[18]。此外，Huang等人提出的无参数层次网络聚类算法（SHRINK）结合了基于密度的聚类和模块化优化方法的优点[19]。在社交网络领域，谢等提出了一种通用的基于标签传播的说话人-听者算法SLPA[2]。进化计算也是一种重要的和有影响力的方法[20，20，21]。社区检测将边缘分为两类：较短的边缘和较长的边缘。在这种情况下，我们可以把注意力集中在大的边上，找出包含SP的社区，然后在这些社区中搜索SP。就我们所知，目前还没有一种利用社区信息来解决加权社会网络中的P2P问题的方法。本文提出了一种新的基于社区检测的最短路径算法（SPCD）。 利用社区信息，SPCD可以缩小降低搜索空间，减少路径的计算时间，同时在一定程度上牺牲精度。它可以在准确性和时间效率之间取得平衡，同时面对不同的问题。本文的结构如下。第2节详细描述了所提出的SPCD算法。第三部分是在五个数据集上的实验。本小节分析准确性和效率。讨论了社区路径数和社区检测方法对SPCD的影响。第四部分是全文的总结，并指出了今后的工作。2. 算法描述在本节中，详细描述了所提出的算法。首先介绍了社区的定义和发现，然后描述了社区图的构造方法。第2.3小节给出了k条最短社区路径。最后给出了子图中的最短路。2.1. 社区定义和检测采用的符号见表1。社区是一组顶点，它们共享共同的属性和/或在图中扮演类似的角色。从质量上讲，社区中节点之间的连接比与网络其他部分的连接更密集、更紧密。对于加权社会网络中的SP，我们定义社区，社区中的连接具有较低的成本，但社区之间的连接具有较高的成本。在本文中，我们使用距离来衡量网络中任何两个节点之间的关系。距离越小，任何两个节点的相关性越高。因此SP问题的目标是找到网络中任意两个节点之间的最小距离。对于其他需要求距离最大值的应用，通过还原评价函数，可以很容易地将其转化为这种最小化问题。一个社区在网络中的演示如图所示。1 .一、j和l之间的边的权重是20，表1符号。符号定义G（V，E）目标网络，其中V{v1，v2，.，v n }是顶点和E是边的集合ei，j2E（i，j2V）顶点i和j之间的非负边s，d源节点和目的地节点C网络社区信息ci（i2V）顶点i的社区c社区中的节点集合c←Ei！;j公共i和j之间的边的集合SG（SV，SE）子图，SV是顶点SE是边的集合从i到j的路径SP最短路径SPSP的加权和社区图SV'Resort theSVSP'子图中的最短路116M. Gong等人/CAAI Transactions on Intelligence Technology 1（2016）114e 123¼¼þ..¼¼Fig. 1.我们定义的社区侦查。图3. 社区之间的边缘可以取代路径。比0.2大得多的i和j之间的边的权重，即eij<$ejl。 因此，根据我们对社区的定义，节点i和j被聚集到同一个社区（c ic j），而l被聚集到另一个社区（c js c l）。Xie J. et al.[2]提出了一个通用框架，该框架使用说话者-收听者标签传播算法（SLPA）来检测社区，并将较大的边缘聚类到加权网络的社区中。在这种情况下，我们不能直接使用谢的方法。我们在执行SLPA之前反转目标网络。反向网络的获得如下。首先，找到边的权重的最大值，即最大边成本，用maxe表示。其次，生成一个正值1或任 何其他正 值，并 与maxe相加 ，用maxe'表示 ，即maxe'maxe1。创建正值是为了防止最大边在下一步中变为零。则反转网络中的边的成本为maxe'减去原始对应的非负成本。如果成本为零，则边的成本保持不变，我们可以得到反转网络（图2中的示例）。通过上述步骤，将原网络中的较大边反转为反转网络中的较小边，使得对反转网络执行谢氏方法所和e_jd，换句话说，e_ij_z_e_sd，所以P_ij可以用来代替P_sd，并且我们可以在搜索从节点s到节点d的最短路径时关注社区之间的边。根据上述分析，我们可以基于社区检测的结果来构建社区图CG（CV，CE），其中CV中的每个顶点代表原始网络的一个社区，而边CE是原始网络的一个社区。最低成本之间的每两个社区分钟！←E.与社区间的边相比，社区中的边的代价较小，可以暂时忽略，因此我们将社区中的所有节点视为一个节点，也就是说这些节点所在的社区就是社区图的节点。社区之间可能有多条边，我们选择最小代价边作为社区图中相应社区节点之间的连接。SP问题的目标是搜索最小路径，因此在这一步中我们选择最小代价边。然后，我们将原始网络建模为一个新的加权社区图。参见图4中的示例。原始网络被聚类为三个社区，因此社区图具有三个节点CV{cv1，cv2，cv3}。社区图中的边ce1，2等价于社区1之间的最小代价边网络是符合我们社区定义的社区信息。和2分钟。←--E-1-;-2-.！-1/4：0，例如ce1,2 四分之四以类似的方式，2.2. 构建社区图为了充分利用网络社区信息，我们构建了社区图。根据我们对社区的定义，社区之间的这些边具有较大的代价，因此我们可以使用社区之间的边来表示这些路径。图 3，我们知道eij大于esi图二、将网络转换为反向网络。得到边ce1，3<$3.3和ce2，3<$8.0。2.3. K条最短社区路径为了在原网络中找到SP，首先要找到包含SP的最短社区路径见图4。构建社区图。M. Gong等人/CAAI Transactions on Intelligence Technology 1（2016）114e 123117j j j j j jj1/4fg图五、在社区图中的最短路径社区路径是社区及其相邻社区。直观地说，社团图的规模远小于原始图的规模，因此可以有效地获得SPk2.4. 子图中的最短路我们利用k条最短社区路径 到 建立搜索子图。可能有两个社区路径相交，例如sp1/4（c1，c2，c3，c4，c5，c6）和sp 2/4（c 3，c 4，c 5，c 6）。sp21/4（c11，c32，c3，c4，c5，c19）具有相同的社区（c3，c4，c5），所以我们得到搜索社区C'^c1，c2，存在SP不包括在最短社区路径中而是包括在第二短或第k短社区路径中的情况，因此下一步是计算k个最短社区路径。K条最短路径问题是指按费用递增的顺序找出从源节点到目的节点的前k条路径。如果社区图中从源社区到目的社区的路径数小于k，则选择所有路径。该方法将原始网络建模为社团图。原网络中的真正最短路径包含在社区图中。而且，找到实际最短路径的概率很高然而，我们不能忽视的情况是，真正的最短路径不是在最短社区路径中得出的，而是在k条最短社区路径中的另一条路径中得出的。基于上述分析，我们计算出k最短社区路径SPk{sp1，sp2，<<<我们使用Yen的算法[22]来找到从源社区cs到目的社区cd的确切SPk（参见图5中的示例）。当图中从s到d的路的数目小于k时，我们将所有存在的路作为SPk。如果s和d在同一个社区中，最短的社区路径是社区，k最短争取k条最短社区路径的交集。接下来我们得到子图SVc1;c2;例如，我们得到一组子节点从原始图中提取SV^SE等于图第六章用我们的方法缩小了图形的规模118M. Gong等人/CAAI Transactions on Intelligence Technology 1（2016）114e 123¼j j <$j¼原始图中的对应节点，例如se1，2 e5，3 子节点1从原始图节点5中排序，子节点2从3中排序。接下来的步骤是通过子图中的SP al-tax m计算SP'，但是我们得到的SP'中的节点来自SV'，所以我们需要根据排序从SP'中得到原始SP。如果SP'1，3，...，n，我们想要的SP是5，8，.，88.路径SP SP '的开销。从上面我们知道SV是V的一部分，换句话说，子图比原始网络小得多，所以我们可以用更少的时间找到SP。该算法利用社区信息构建社区网络，寻找社区路径，然后从原网络中提取子图。最后，从子图中得到SP。这个社区路径可以帮助我们缩小搜索空间的大小，从而节省搜索时间（参见图6中的示例）。高精度需要较大的k值，但k值越大，时间复杂度越高，因此必须设置适当的k值。该算法的一般算法流程的伪代码如图1所示。3. 试验与分析我们的算法SPCD在Matlab 2012a中实现所有实验都在具有2个2.00 GHz Intel（R）Xeon（R）CPU E5-2620和64GB内存的Windows 7服务器上运行3.1. 数据集我们在五个合作网络中进行了实验，其中节点代表科学家，两个科学家之间的联系是通过他们共同撰写一篇或多篇科学论文来建立的。协作网络有一个更promising的数据源，这个网络在某些方面比许多其他网络更真正的社交网络[3]。(1) 网络科学领域的合著者：网络科学家的合著者网络（网络科学）工作的网络理论和实验，包括出版物，直到2006年初，由M。Newman，2006年5月[23]。该网络共有来自各个领域的1589名科学家[23]。(2) 高能理论合作：1995年1月1日至1999年12月31日期间在高能理论电子印刷档案[3]上发布预印本的科学家之间的合作者加权网络。该网络包含8361个节点和15751条边。(3) Astrophysics collaborations（astro-ph）：1995年1月1日 至 1999 年 12 月 31 日 之 间 在 Astrophysics E-PrintArchive[25]上发布预印本的科学家之间的合作关系的加权网络。该网络包含16706个节点和121251条边。(4) 凝聚态物质合作1999（con-mat）：1995年1月1日至1999年12月31日之间在凝聚态物质电子印刷档案[26]上发布预印本的科学家之间的合作者加权网络。该网络包含16726个节点和47594条边。表2核实验数据集的一些基本统计量。洛斯阿拉莫斯国家实验室年度论文作者优势199687488766919954641359181998184966112821997125825144021999300143416840200032818032716920025032101233612001416191423438200470028764672220035612153296942005724269029161200667330265326520078103894679012008787400887006200987639169640620109355643165598201112586000170792201213806823219627201313107370244326201413067035273598M. Gong等人/CAAI Transactions on Intelligence Technology 1（2016）114e 123119B¼j≤我们的方法时间是所有500个随机并给出了节点对和最小值、最大值(5) 核实验数据集（nucl-ex）：1994年12月至今发表在洛斯阿拉莫斯电子印刷档案馆[27]。我们构建了1994年至2014年每年的网络，并进行了统计。仅通过姓氏和首字母[3]和权重[5]识别每个作者的作者（即顶点）由M定义。纽曼这些收集的规模列于表2和表6。3.2. 绩效评价我们评估所提出的算法在搜索过程中的SP节点之间的准确性。我们随机选择500个现有的节点对，并为每个数据集独立运行10次，以获得平均精度。近似误差aper为：XN .dbi-din，1/1D我其中di是第i对节点的实际距离，di是近似值。实际的距离是由Dijkstra算法[28]测量的，时间复杂度为O（n2）。它可以优化为O E V log V一个Fibonacci heap[29]。我们必须保证在某些情况下不同的最低价格。将本文中所有数据集的最小值设置为0.05。改善时间：XN ti，效率1/1N~ti的算法，t是通过其中ti是dijkstraei3.3. 实验结果由于网络太多，因此我们将实验结果显示在两个表中（表3和表7）。在表7中，我们可以看到，在0.05的高精度的情况下，通过我们的方法，时间效率提高了许多倍。数字是括号中的aper。对于网络科学网络，aper为0.0363，近似等于零，而eff为387.58。在其它三个网络中 ， 最 大 aper 为 0.0479 的 con-mat 小 于 0.05 ， effs 为2740.48。对于天文ph网络，其效率接近3000，aper为0.0473。结果表明，SPCD可以在极小的子图网络中找到SP。在这些网络中（见表3），我们在大多数情况下将k设置为1，1998年的有效性为104.7，1995 - 1997年的有效性小于100，但它们的有效性均为零。这意味着我们可以找到准确的SP与提高效率。2010年的最大有效值为701.9，自2004年以来，有效值均大于300表3aper和effe中的核实验结果。年纸上1995026.791996021.661997062.6119980104.719990.007120.320010.02119220000.00515720030.028173.520020.00525620040.027340.220050.006306.820070.037290.920060.048305.120080.025250.420090.043316.720110.037540.820100.046701.920120.0594.5720130.04394.120140.047201.7纸页1/4N120M. Gong等人/CAAI Transactions on Intelligence Technology 1（2016）114e 123≤表4小规模网络中合适的k值核实验网络科学199519961997199819992000200120022003200420052006K1111222122233aper000000.0030.0010.0040.0120.0080.0020.0170.014表5大规模网络中合适的k值核实验hep-th astro-ph con-mat20072008200920102011201220132014K3655864591214aper0.0090.0110.010.0040.0110.0490.0390.0470.0470.0470.048表6一些基本的统计研究的合作网络。网络网络科学赫普特天体ph康马特的节点158983611670616726顶点总数27421575112125147594表7计算效率：计算SP和eff的时间。网络科学赫普特天体ph通信垫aper0.03630.04720.04730.0479EFF387.58960.652915.972940.48虽然2012年的EFF仅为94.51，但显然我们的算法是有效的。3.4. 参数k随着最短社区路径数k的增加，虽然k被设置为1，在大多数情况下，对于小aper的核实验数据集，如果我们要求aper为0.05，则大规模网络需要更大的k。在1995年到2006年的小规模网络核实验和网络科学中（见表4），我们只需要一个很小的k就可以得到一个精度很高的最短路径（99%以上），但是我们可以非常有效地找到这些路径在大规模网络中，对于相似或所需的精度，需要大k（见表5），特别是在hep-th，con-mat和astro-ph中。在这种情况下，我们的算法在效率上仍然有价值的效果。对于小规模的网络，较小的k可能会得到更好的结果，但对于大规模的网络，我们需要选择合适的k来获得满意的结果。如图7所示，随着k值的增大，计算结果的精度大大提高。如图7所示，aper随着k的增加而迅速减小，这表明所提出的方法可以有效地找到SP的范围。从实际应用的角度来看，可以选择合适的k值来满足精度要求。我们知道，k与子图的大小有关，因此，子图的大小将增加，效率也将提高。图第七章核实验数据中含k的论文M. Gong等人/CAAI Transactions on Intelligence Technology 1（2016）114e 123121-随着k的增大，搜索次数减少。图8证实了我们的分析。在核实验网络数据集中，随着k的增大，搜索最短路径的效率会降低。考虑到这一点，我们需要一个较小的k来保护效率，即一个很大的eff。在astro-ph，con-mat和hep-th中，eff也随k的增大而变差。从以上实验结果可以看出，准确率和效率是该方法需要优化的两个目标。增大k可以提高计算精度，但会降低计算效率。我们需要大的eff和（1aper）（小aper是完美的），这是可取的，但我们不能从图9中使两者都很大。那么我们需要权衡精度和效率，aper小于0.05在我们的实验。SPCD利用社区信息来搜索SP，因此需要一种准确的社区发现方法。我们选择了两种不同的方法，BGLL和SHRINK一般网络和SLPA的社会网络。图10比较了三种社区检测方法返回的aper。实验结果表明，SLPA和BGLL的性能较好，而SHRINK的性能较差，不能用于本方法。在SLPA和BGLL之间，SLPA从nucl-ex2010、nucl-ex 2012到nucl-ex 2014网络较好。在图11中，很明显，BGLL具有最差的效率，即使它在核中可能优于SLPA。图八、核实验数据集中带k的eff图第九章效率与效率的冲突。122M. Gong等人/CAAI Transactions on Intelligence Technology 1（2016）114e 123图10. nul-ex数据集上的三个社区的论文图十一岁三个社区对nul-ex数据集的影响ex2012，所以SLPA是本文和eff认为的最适合SPCD的社区发现方法4. 结论本文提出了一种新的有效的P2P最短路径问题的解决方法。我们的方法是基于社区结构，它可以分为两个部分的边缘根据成本。通过构造社区图，缩小了SP的范围，提高了SP的搜索效率。选择合适的最短社团路径数k可以保证近似误差。五个真实协作网络的广泛实验结果网络证明了效率和近似误差。对于给定的极限，我们的算法具有优良的性能。特别地，各种社区检测方法可以用于该算法中。在未来，我们将专注于开发一种启发式方法，结合社会网络社区信息的SP问题加权社交网络。另外，研究适合于社会网络的社区发现算法引用[1] J. Scott，P.J. Carrington，The SAGE Handbook of SocialNetworkAnalysis，SAGE Publications，2011.M. Gong等人/CAAI Transactions on Intelligence Technology 1（2016）114e 123123[2] J.Xie ， B.K.Szymanski ， X.Liu ， Slpa ： Uncoveringoverlappingcommunities in 社 交 网 络 网 络 via a speaker-listenerinteractiondynamicprocess， in ： DataMiningWorkshops（ICDMW），2011 IEEE 11thInternationalConference on，IEEE，2011，pp. 344和349。[3] 法医Newman，Phys.Rev.E64（1）（2001）016131。[4]M. Potamias ， F. 邦 奇 角 Castillo ， A. Gionis ， Fast shortest pathdistanceestimation in large networks ， in ： Proceedings of the 18thACMConference on Information and Knowledge Management ，ACM，2009，pp. 867和876。[5] 法医Newman，Phys.Rev.E64（1）（2001）016132.[6] G.R. Jagadeesh，T. Srikanthan，K. Quek，智能运输。IEEETrans.3（4）（2002）301e 309。[7] S.荣格，S. Pramanik，Knowl.Data Eng.IEEE Trans.14（5）（2002）1029e 1046.[8] H.A. Karimi，J. Intelligent Transp. 3（2）（1996）111e 127.[9]B . Liu，IEEE Trans. 27（4）（1997）436e 448。[10] P. Sanders，D. Schultes，Highway hierarchies hurt exact shortestpathqueries，in：Algorithmse Esa 2005，Springer，2005，pp. 568和579。[11] L. Fu，D. Sun，L.R.计算机，第33（11）（2006）3324和3343号决议。[12] M. Girvan，M.E. Newman，Proc. Natl. Acad. Sci. 99（12）（2002）7821e 7826。[13] 法医Newman，Phys.Rev.E69（6）（2004）066133.[14]F.拉迪基角Castellano，F. Cecconi，V. Loreto，D. Parisi，Proc. Natl.Acad. Sci. U S A 101（9）（2004）2658e 2663.[15]M.E. Newman，M.Girvan，Phys.Rev. E 69（2）（2004）026113。[16]X. Xu，N.尤鲁克岛冯，T. A. Schweiger，扫描：网络的结构聚类算法，在：第13届ACM SIGKDD国际知识发现和数据挖掘会议论文集，ACM，2007年，pp. 824和833。[17]Y.-- Y. Ahn，J.P.Bagrow，S.Lehmann，Nature 466（7307）（2010）761和764.[18] V.D. Blondel，J.- L.纪尧姆河Lambiotte，E. Lefebvre，J. Stat.机甲理论实验2008（10）（2008）10008.[19] J. Huang，H. Sun，J. Han，H.邓，Y.太阳，Y。Liu，Shrink：Astructuralclustering algorithm for detecting hierarchical communities innetworks，in：Proceedings of the 19th ACM International ConferenceonInformation and Knowledge Management，ACM，2010，pp. 219和228页。[20] M.- G.贡湖J. Zhang，J.- J. Ma，L. C. Jiao，J. Comput. Sci. Technol.27（3）（2012）455e467。[21] M.龚俊，刘，L.马角，澳-地蔡湖，加-地Jiao，Phys. A Stat. 403（2014）71和84。[22] J.Y.杨，马纳格。Sci. 17（11）（1971）712e 716。[23] 法医Newman，Phys.Rev.E74（3）（2006）036104。[24] 法医Newman，Proc.Natl. Acad. Sci. 98（2）（2001）404e 409。[25] http://arxiv.org/archive/astro-ph网站。[26] http://arxiv.org/archive/cond-mat网站。[27] http://arxiv.org/archive/nucl-ex网站。[28] E.W. Dijkstra，Numer.数学1（1）（1959）269e 271.[29] M.L. Fredman，R. E.Tarjan，J. ACM（JACM）34（3）（1987）596e615.