关键词： 复杂网络   社团结构   近邻传播   信号传递   节点相似度  

摘要： 社团结构是众多复杂网络的统计特性之一,挖掘网络中存在的社团结构日益受到人们的普遍关注。网络中的社团结构检测本质上类似于传统机器学习领域的聚类分析,其关键问题在于如何定义网络中节点间的相似度。首先提出了基于节点相似度的节点分裂算法SGN,相比传统的基于边界数(betweenness)的节点分裂算法GN,SGN在速度和精度上都有明显改善;接着,在利用各种节点相似度计算方法得到节点间的相似度之后,采用几种经典的聚类分析算法对网络进行社团划分,在模拟数据和真实数据上的实验表明:基于网络拓扑结构信息的signal和regular方法优于基于网络节点局部信息的Jaccard方法,而且对于复杂网络社团划分问题,如果选择好的网络节点相似度构造方法,已有的基于相似度矩阵的聚类分析算法都能快速有效地对网络社团进行划分。

关键词： 社团结构   模块密度   核k-means方法   谱分方法  

摘要： 为有效地检测复杂网络中的社团结构,优化模块密度函数,展示模块密度函数怎样被优化框定到谱分聚类问题,提出一种谱分算法,进一步对该算法进行时间复杂度分析。在一个经典的真实世界网络中检验该算法,并与基于模块密度的直接核方法及基于模块函数的谱分方法做比较。特别地,当网络中社团结构变得模糊时,实验结果显示,该谱分算法在发现复杂网络社团上是有效的。

关键词： Corporate bond index returns   Smooth transition regression model   Model selection  

摘要： This paper investigates the time-varying corporate bond index returns in a multi-factor smooth transition regression model. We find that expected index returns vary between weak and strong economic regimes, where the transition from one regime to the other is governed by the 3-quartered growth of industrial production. Weak economic regimes are characterized by low growth of industrial production, vice versa for strong economic regimes. Further, risk factor sensitivities are generally more negative in strong economic regimes than in weak regimes, implying that index returns are low when economic conditions are good and high when economic conditions are poor. (C) 2010 Elsevier B.V. All rights reserved.

关键词： 复杂网络   社团结构   模块密度   社团检测  

摘要： 近年来，复杂网络逐渐成为描述与分析现实复杂系统的重要工具而备受关注。复杂网络的大规模性、强耦合性、局部性等特点促使研究人员通过局部特性来刻画与研究整体特性。其中，社团结构作为一种局部研究方法在计算机科学、生物信息学和社会学等多个领域都有重要的意义。 在社团检测算法中如何有效量化社团划分结果及如何设计出高效、准确的算法是两大关键问题所在。为了解决社团量化的问题，Newman等在对比真实网络与随机网络的基础上提出了模块度函数。尽管最大化模块度函数属于NP-难问题，但绝大多数算法都是基于优化模块度函数。针对于模块度函数存在的分辨极限问题，李等通过对比社团内部边和外部边密度提出了模块密度函数，并证明了该测量标准可以在很大程度上克服分辨极限问题。但是模块密度只能应用于无权图。在真实网络中，给每一个节点赋予相同的权重并不合理。为了克服该缺陷，本文提出了一种泛化的模块密度。并设计出基于优化加权模块密度的模拟退火算法。实验结果表明该测度更加有效的刻画网络社团结构。 为了进一步拓展泛化的模块密度的应用，本文提出了一个基于泛化模块密度函数的可以对蛋白质相互作用网络的功能模块进行检测的算法，并开发出相应的可视化软件。实验结果表明该算法不仅可以快速检测出蛋白质相互作用网络中的功能模块，同时可检测出具有重叠结构的蛋白质功能模块。

关键词： 复杂网络   社团结构   社团检测   随机游走   有向网络   无向网络  

摘要： 复杂网络研究作为一个新兴的学科方向,极大地吸引了来自不同学科研究人员的广泛关注。对复杂网络的定性和定量特征的研究,有助于揭示复杂网络表示下的不同复杂系统中普遍存在的一般规律,在生物科学、社会科学等诸多学科中具有重要意义。社团结构是复杂网络的一个关键结构规律,因此准确分析复杂网络的社团结构是复杂网络研究中的一个非常重要的课题。 在复杂网络社团结构的分析研究中,模块度度量(及其变种)起了很重要的作用,催生了一大类重要的社团结构分析方法。但是这类通过对模块度度量(及其变种)优化来获得网络社团划分的方法存在分辨率问题,从而极大地限制了基于模块度方法的有效性和应用广度。 另一方面,目前社团结构分析研究主要集中在无向网络上,系统地直接分析有向网络社团结构的研究还远远不及对无向网络社团结构的分析研究。实际上,当前有向网络社团结构划分的普遍做法是通过简单地忽略有向网络中边的方向,将有向网络当成无向网络分析。这种方法在大多数情况下由于忽略了有向网络中边的方向包含的重要拓扑结构信息,从而无法正确有效地划分网络的社团结构。另外,在有向网络上扩展多数无向网络社团结构的分析方法往往不是简单的工作。 本论文从模块度度量的相关问题出发,将无向二元网络上模块度优化时的分辨率问题的分析扩展到无向加权网络中,并在此基础上提出了一种结合网络预处理的增强型模块度优化社团结构分析方法。通过分析无向网络上的模块度优化产生分辨率问题的条件,提出通过有效地获得关于社团之间边的信息来处理模块度优化时可能产生的分辨率问题。基于网络上的动力学过程反映网络的潜在结构这一事实,利用无向网络上的随机游走过程获取关于社团内部边和社团外部边的信息,并通过边的迭代重加权操作使得网络边的权值不断向社团内部集中,而社团之间的边权值越来越小,从而有效地克服模块度优化时的分辨率问题。实验分析表明,这种结合了网络预处理的无向网络社团分析方法极大地增强了基于模块度优化的无向网络社团结构分析方法的有效性和应用广度。 针对传统的有向网络社团结构分析方法简单忽略边的方向将使得社团划分不准确的问题,提出了一种基于有向网络嵌入的有向网络社团结构分析方法。该方法通过在有向网络上扩展无向网络的网络嵌入分析,从有向网络嵌入目标函数关联的拉普拉斯矩阵中分离出包含了边的方向信息的对称矩阵作为有向网络对等的无向加权网络的邻接矩阵,并导出一种关于有向网络社团结构划分的新模块度定义。一方面,新模块度度量进一步解释了有向网络社团的另一种物理内涵:同一社团内的结点是最大程度保持了有向网络局部结构的相邻结点集合;另一方面,它建立了有向网络与某种无向网络的联系,这种联系表明有向网络的社团结构可以通过应用已有的无向网络社团结构分析方法可靠并且有效地在所导出的无向网络上分析得到。 进一步扩展了基于有向网络嵌入的有向网络社团结构分析方法的分析思路,提出了一种基于边的方向信息抽取的有向网络社团结构分析方法。该方法基于具有社团结构的有向网络上的流运动将更加容易地在社团内部结点之间进行的事实,通过有向网络上的PageRank型随机游走过程有效地抽取有向网络边的方向包含的信息,并采用适当的相似性函数将其转化为边的权值与有向网络中边的互联性集成共同定义有向网络的社团结构。在抽取足够多的关于边的方向信息后,通过忽略边的方向将有向网络的社团划分问题等价为所导出的无向加权网络的社团划分问题,在保持社团结构划分准确性的同时有效地简化了有向网络社团结构划分问题的分析,避免了无向网络分析方法常常难以直接扩展到有向网络社团结构分析中的问题。 在分析前述关于无向网络和有向网络社团结构分析方法的可统一性基础上,提出了一种基于网络结点间消息传递的社团结构分析的一致框架。通过随机游走将网络结点表示成向量空间中的点,并以此有效地定义表达结点属于同一社团可能程度的相似性。利用affinity propagation算法的消息传递机制将网络的社团结构划分问题转换成社团领导者的推选过程。在实际网络和标准测试网络上的分析表明,这种消息传递的网络社团结构分析框架能够:(i)有效地处理分辨率问题,即有效地分析那些通过模块度优化会出现分辨率问题的网络的社团结构;(ii)在一个一致的框架中分析有向网络和无向网络的社团结构;(iii)揭示网络中可能存在的多级社团结构。

关键词： 社团检测   谱分析法   近邻传播   局部社团发现   可视化实验平台  

摘要： 摘要 随着复杂网络理论研究的不断深入及在各领域的应用,其所具有的社团结构特征吸引了广泛的关注。寻找和分析复杂网络的社团结构对于反映和理解整个网络的构成和功能有重要的意义。本论文主要研究社团结构检测问题,提出了基于谱分析法和近邻传播的算法、基于局部发现的算法两种检测方法,并建立了可视化实验平台。 论文对传统的Normal矩阵谱分析法及近邻传播算法进行了研究。传统的Normal矩阵谱分析法在网络社团结构不明显的情况下难以得到理想的结果,针对这个问题,论文提出了一种基于谱分析法和近邻传播的社团检测算法。该算法采用近邻传播算法对多个Normal矩阵特征向量的元素进行聚类分析,根据聚类结果来获得整个网络的社团检测结果。这种基于谱分析法和近邻传播的算法在无需预先知道社团数目的前提下对于社团结构不明显的网络也具有较好的检测效果。 论文针对目前部分算法时间复杂度较高、无法对大规模网络进行检测的问题提出了一种基于局部发现的社团结构检测算法。论文设计了一个用于快速寻找指定节点社团成员的局部社团检测算法,通过对该算法进行扩展,不断将检测出的局部社团成员从网络中移除来进行网络整个社团结构的检测。这种基于局部发现的社团检测算法在不需要预先知道社团数目的基础上具有较好的时间复杂度,并且检测效果也比较理想。 论文设计和实现了一个可视化实验平台,该平台能够对社团检测结果进行可视化显示,并计算相应数据。使用该平台将论文提出的两种算法与GN算法、CNM算法进行对比,实验数据表明,基于谱分析法和近邻传播的算法在无需预先知道社团数目的基础上无论网络的社团结构是否明显都具有较好的检测效果,基于局部发现的算法具有很好的计算效率、无需知道社团数目并且检测效果也令人满意。

关键词： 复杂网络   社团结构   模块密度   核k方法   非负矩阵分解  

摘要： 为有效地检测复杂网络中的社团结构,优化了评估与发现社团的模块密度函数(即D值)。通过模块密度的优化进程,证明了模块函数的最大化与非负矩阵分解目标函数(SNMF)的等价性。基于这种等价性,设计了一种新的基于模块密度函SNMF算法,并且讨论了该算法的复杂性。在一个经典的计算机产生的随机网络中检验了该算法,特别地,当社团结构变模糊时,实验结果表明该算法在发现复杂网络社团上是有效的。

关键词： 社团结构   模块密度   核k-means算法  

摘要： 为揭示复杂系统中的结构与功能之间的联系,复杂网络中的社团发现成为一项最基本的任务。最近,李等人提出了一种用来评估社团质量的函数,称之为模块密度函数(即D值),并利用一个核矩阵给出了模块密度目标函数与核k-means方法之间的等价性。基于这种等价性,通过过渡操作的核矩阵来优化模块密度函数并提出了一种新的核k-means算法。实验结果表明,这种算法在发现复杂网络社团上是有效的。

关键词： 权重自相似   加权网络   社团结构   谱分析算法  

摘要： 提出了权重自相似性加权网络社团结构评判函数,并基于该函数提出一种谱分析算法检测社团结构,结果表明算法能将加权网络划分为同一社团内边权值分布均匀,而社团间边权值分布随机的社团结构.通过建立具有社团结构的加权随机网络分析了该算法的准确性,与WEO和WGN算法相比,在评判权重自相似的阈值系数取较小时,该算法具有较高的准确性.对于一个具有n个节点和c个社团的加权网络,社团结构检测的复杂度为O(cn2/2).通过设置评判权重自相似的阈值系数,可检测出能反映节点联系稳定性的层化性社团结构.这与传统意义上只将加权网络划分为社团中边权值较大而社团间边权值较小的标准不同,从另一个角度更好地提取了加权网络的结构信息.

关键词： 复杂网络   社团结构   路径映射理论   检测算法  

摘要： 现实世界中的网络具有规模巨大、结构复杂的特点，它们由各种实体以及实体间错综复杂的关系构成，其存在形式既可以是有形的（输电网络、交通网络、神经网络），也可以是无形的（万维网、社交网络、文献引用网络）。简单的图论已不能满足研究这些现实规模巨大且结构复杂的网络的需要。兴起的复杂网络理论，很好地解释了很多关于现实网络的特征，如小世界、无标度、分形等网络模型特征，网络同步等的网络动力学特征以及社团组合的网络结构特征等。复杂网络的研究目的就是要揭示隐藏在各种现实实体关系中的规律性，并探索复杂网络理论在工程技术领域中的应用。\n 本文围绕现实世界网络特性和复杂网络模型展开研究，集中研究了网络社团结构检测与最短路径映射策略这两个目前较具有代表性的热点问题。在研究过程中，采取了理论分析和计算机仿真相结合的手段，在理论和实践方面验证了研究的正确性和可行性，主要研究内容如下。\n 研究了复杂网络的结构。包括一般现实网络所具有的小世界特性，无标度特性，并给出了实例说明，然后分析了各种网络结构模型，包括随机网络，小世界网络和无标度网络，加权网络等，重点阐述了这些网络模型的具体构造方法，这些网络模型在后面的计算机仿真分析中可帮助验证算法的性能。\n 研究了复杂网络社团结构递归过滤检测算法。针对无权网络，分析了社团结构的产生机理，提出了一种能一次过滤多条边分裂网络的社团结构递归过滤检测算法。在该算法中，定义社团递归演化系数M控制分裂进程，通过优化子网络M将子网络递归过滤分裂演化为局部社团，最终得到社团结构。理论分析和实验结果表明，该算法一次过滤多条边并行分裂网络，检测一个具有m条边和c个社团的网络，该算法最多只需将原网络分裂c+1次，计算复杂度为D（㎡+（c+1）m）。除此以外，该算法能使局部社团根据它们向外边密度按由小到大的顺序被检测出来。\n 研究了复杂网络权重自相似特性及其社团结构检测算法。基于边权重自相似原则，研究如何将加权网络划分为若干个边权值在社团内部分布均匀而社团间分布不均匀的社团。为了达此目的，本文提出了一个加权模块度函数，根据该模块度函数，很多针对多无权网络的社团结构算法只需简单的改动就能应用于加权网络社团结构分析中。基于该模块度函数，本文提出了一种谱分析算法，应用该算法对计算机模拟网络和现实网络进行分析，研究表明与传统的加权网络社团结构检测算法相比，该算法在检测本文所定义的社团结构时具有较高的准确度和精度。对于一个具有n个节点和c个社团结构的网络，算法复杂度仅为O（cn2/2）。通过调整边权重自相似阀值系数，该算法可揭示加权网络中特殊的边权值相似分布的层次化结构，使我们能获取加权网络中更多关于结构的信息。\n 研究了一种复杂网络最短路径自组织映射算法。针对复杂网络的特殊结构，提出了一种基于热流量传递的最短路径自组织映射方法。由于该方法属于完全局部扩散方法，因此具有较高的速度。基于节点温度升高总是沿着距高温源节点最短路径的贪婪原则，该方法准确性较高。与全局扩散方法BFS不同的是，该方法通过比较局部节点温度信息并行自组织最短路径，不但映射速度比BFS快，并且可使网络中的额外信息交换量大大减少。设网络有n个节点，m条边，传导时间设为t，积分时间间隔设为△t，则映射各节点到源节点的最短路径总计算复杂度为O（mt/△t），平均每个节点仅为O（mt/n△t）。\n 研究了无线传感网络自组织路由方法。借鉴最短路径自组织映射思想，通过以节点的剩余能量，路径受阻状况及节点失效为节点路由表建立与维护的依据，设计了一种自组织路由协议。在该协议的最优路由配置阶段，每个传感节点的传输路由通过局部邻居节点的反馈信息比较确定，传输可靠性通过路径修复来保证。由于避免采用多路径传输，不但延长了节点能量使用寿命，还降低了数据碰撞概率，从而提高了传输成功率。最后，通过OPNET仿真将该协议与两个代表性的协议AODV和DSR进行了性能比较，结果表明本文所模拟的相同场景下，自组织路由协议在数据成功传输率、平均包延时和网络寿命上与AODV和DSR相比，具有较高的优越性。