关键词： 社团检测   复杂网络   标签传播   网络分析  

摘要： 标签传播算法的社团检测原理简洁、时间复杂性低,产生了大量的基于标签传播的社团检测方法,亟需系统性总结.本文首先分析概括了标签传播算法存在的问题、成因和挑战;然后主要从以下几方面分别阐述了其研究现状,汇总了相关方法采用的策略,分析比较了代表性算法:1)提高算法性能,2)解决不确定性问题,3)解决标签震荡现象,4)解决平凡检测问题,5)重叠社团检测,6)动态社团检测;最后总结了代表性算法的适用场景,并对该类算法的难点和发展趋势进行了展望.

关键词： 复杂网络   社团检测   电网分区   功能性社团结构   拓扑性社团结构  

摘要： 电网分区是运行和保护电网的重要课题。以关联强度代替传统的邻接矩阵,定义电气关联强度(ECS)用来反映电网中任意节点之间的电气特性,并基于发电机节点和负荷节点之间的供电关系提出供电关联强度(PSS)。在经典的模块度(Modularity)基础上,结合供电关联强度提出供电模块度(PS-Modularity)的概念,并基于此对Newman快速算法进行改进,以自动识别供电社团结构。

关键词： 社交网络   社团检测   社团隐私   社团安全   社团隐藏  

摘要： 社团是社交网络的重要特征,社团检测技术的发展给网络用户带来隐私泄露的危险。如何保护敏感的社团信息不被泄露,保障用户与社团安全已经成为网络安全领域的研究热点。近几年,社团保护技术取得了初步进展,但针对社交网络中的社团隐私或社团安全研究进展综述较少,不利于该研究方向的长远发展。因此,主要针对社团结构隐私方面的研究进展进行综述,对最新的相关研究成果进行系统地归纳、总结、比较,并展望了未来的研究方向。

关键词： 复杂网络   神经网络   模块度函数   社团结构   特征向量  

摘要： 针对复杂网络的社团结构提取问题提出了两种新的复杂网络社团结构提取算法:连续神经网络(CNN)算法和离散Hopfield神经网络(DHNN)算法,对提出的两种社团结构提取算法在8个实际网络上进行了仿真实验,结果表明,DHNN社团结构提取算法比CNN算法及Newman的特征值特征向量算法得到的Q大.同时DHNN算法不需要进行求特征值特征向量之类的计算,只需要进行简单的加法乘法运算便能提取到网络中的社团结构.即所提算法特别是DHNN算法具有强大的计算能力,可以提取出规模更大的复杂网络中的社团结构.

关键词： Potts Spin-glass   合谋   复杂网络   社团检测  

摘要： 工程招投标作为项目前期资本规模控制的一种重要方式,在项目全生命周期的成本控制方面扮演着至关重要的角色,并随着经济的发展在各行各业得到了广泛的应用并取得良好的效果,为各项投资节省了大量资源,但是由于建筑行业本身的特点,招投标阶段被认为是腐败现象频发的阶段,存在包括围标串标等诸多不合理行为,甚至在一些地区存在着“无标不围、无标不串”的严重情况。而如何识别合谋行为一直是监管机构的痛点和难点。本文从影响合谋行为发生的主要因素及其表现形式,分析了国内外对合谋行为界定的主要方法,提出将行为科学中的复杂网络技术应用到建设项目招投标阶段的合谋行为检测中。广东省是我国实施招投标较早的地区,其招投标数据完善程度较高。因此,文章利用文献调研法对需要收集数据和模型对应指标进行统计分析,采用爬虫技术获取广东省2015-2020年间关于招标、资格审查、中标以及投标企业负责人等信息,建立ACCESS数据库对以上信息进行整合,建立数据之间的连贯性。利用python3.6.3对数据中的缺失值、噪声值及异常值进行预处理,以Graph模块建立投标人无向加权复杂网络,结合基于动态社区检测方法的Potts Spin-glass算法进行社团结构挖掘。该算法相较其他方法,具有自动识别最稳定基态达到最优划分的优点。为了使社团划分更加合理,文章首先将社团划分为10个较大社团,针对社团中的典型社团结构,对其进行二次社团结构挖掘,分析特征值,验证了该算法对合谋行为挖掘的适用性,并对其他社团结构二次挖掘,得出最优投标人社团结构。最后,将该算法与其他算法进行时间复杂度对比,验证spin-glass算法在社团结构挖掘方面的优势及适用性,利用项目投标报价规律分析和网络中公开的围标串标行为处罚通知对挖掘出的社团结构进行验证,进一步证明了复杂网络中社团结构挖掘技术对招投标合谋行为识别的正确性和适用性,并结合大数据和区块链技术,提出相应的合谋行为治理机制。

关键词： 有向无环网络   社团检测   聚类   近似度   网络嵌入   节点角色  

摘要： 有向无环网络是一类特殊的不包含环的网络,普遍存在于生物学、遗传学、金融学等领域。社团是网络介观尺度上最突出的结构特征之一,对网络功能有着至关重要的影响。网络社团结构检测和分析已成为一个重要的主题,吸引了众多不同领域学者的关注。对有向无环网络中社团结构的检测是深入理解整个网络功能的重要途径之一。通常,由实际系统构建的有向无环网络的边具有对抗或相似两种关系。现有的大多数社团检测算法并不适用于边对抗有向无环网络,对于边相似有向无环网络也存在与聚类算法割裂、复杂度高的问题。针对以上现象,本文探究了两种类型的有向无环网络中的社团检测,主要研究内容和成果如下:提出了可用于寻找边对抗有向无环网络中社团的Katz-Simrank方法,分别利用Katz和Simrank++近似度捕捉节点的序和相似度信息,将有向无环网络中的社团检测问题转化为有权无向网络中的派系检测问题。在对四种不同类型的有向无环网络的测试中,该方法获得的社团划分的标准化互信息、调整兰德系数、同质性和多样性指标均优于先前的基于模块度的方法和分层方法,验证了该方法的有效性。针对边相似有向无环网络,利用Katz近似度来刻画节点之间的相互作用紧密程度,将其作为它们的相似度对相似度量图嵌入(FVERSE)算法进行改进,结合Kmeans提出基于Katz-FVERSE的社团检测框架。在各人工网络和真实网络上进行测试后发现,该框架获得的标准化互信息和模块度指标有87.5%的比例超越和接近其他最优框架,验证了该框架的有效性。将基于Katz-FVERSE的社团检测框架分别应用于不同度分布的人工引文网络和真实网络中,发现基于社团结构的节点角色和节点重要性之间存在显著联系。多数边位于所属社团和许多边连接不同社团的中心节点有81.4%和75%的概率是重要节点,远高于其他角色的节点并具有统计显著性。因此,可以通过社团检测来判断网络中节点的角色从而实现重要节点的预测。

关键词： 进化计算   标签传播   密母算法   强化学习   网络嵌入   图自编码器  

摘要： 现实世界的许多事物,如电力系统、社交网络、交通网络等,都可以抽象成由节点和其联结关系构成的复杂网络。社团检测和网络嵌入是复杂网络中两个重要的研究方向。一方面,社团是复杂网络在结构特性上的一个重要体现,不仅可以反映社交网络中的兴趣团体,还可以反映蛋白质相互作用网络中的调控模块,因此社团检测对于理解网络中信息传播,发现网络中功能模块都起到关键作用。另一方面,网络嵌入通过将高维稀疏连接关系映射至低维向量空间,克服了处理高维非线性数据的困难,为后续在分类、识别和预测等任务上使用机器学习算法创造了有利条件。然而这两个研究方向面临着诸多困难:在社团检测问题中,多样化的现实情境和图结构的非线性性质对如何定义合适的社团目标函数提出了挑战,同时大规模的节点数量亦要求社团检测算法具有高效的搜索方式;在网络嵌入问题中,如何突破传统的一阶二阶相似度定义引入社团结构相似度,并在网络嵌入学习算法的可导目标函数中加入社团结构信息是一个挑战。基于以上挑战,本文一方面研究并设计了基于进化计算的社团检测算法中的三个关键算子:初始化算子、交叉算子和局部搜索算子;另一方面,针对如何在网络映射中保留社团结构信息,提出了一种使用图自编码器和进化计算交替优化网络嵌入的方法,主要研究工作如下:（1）基于启发式采样和等价映射的社团检测进化算法大多数基于进化计算的社团检测算法没有处理个体交叉时社团编码存在一部分差异的问题,而且在生成初始解时缺乏对物理假设的考虑。针对上述问题,本文提出了采样算子和学习算子。前者借鉴标签传播算法的思路从发展的角度看待社团的变动,认为社团划分采样于由图矩阵支配的信息传播过程;后者在海明距离的意义下,构建了寻找两个个体之间等价映射的贪心算法,来消解一部分编码差异的问题。进而本文提出综合两者的基于启发式采样和等价映射的进化算法用于处理社团检测问题。通过多种现实网络的独立对比实验,分别证明了学习算子和采样算子的有效性,以及整体算法相对以往基于进化计算的社团检测算法的优势。（2）基于置信度上限和大规模邻域搜索的社团检测密母算法大部分的基于进化计算的社团检测算法中,局部搜索算子往往采用的是传统的爬山法和模拟退火等缺乏针对性的搜索方法。本文引入了强化学习和大规模邻域搜索的框架,并针对社团检测问题建立了社团评分函数、移动收益函数的概念来使用基于强化学习范式的控制策略,建立了破坏算子和修复算子的概念来使用大规模邻域搜索的框架。两者在密母算法的框架下结合起来以利用不同社团评分函数的优势。实验表明,我们提出的局部搜索方法相对传统的启发式局部搜索算子收敛速度快,收敛上限高,同时基于不同社团评分函数的局部搜索算子在密母算法中的重组算子影响下组合具有更大的优势。（3）基于进化计算与图自编码器的网络嵌入学习算法将高阶结构信息以及社团所暗含的信息融入到网络嵌入的学习之中一直是人们所期望的事情,然而无论是传统的矩阵分解方法还是现在流行的深度学习方法都是从重建损失函数的角度优化嵌入问题,从而难以引入不可导的离散形式的社团结构函数。本文一方面建立了表示重叠社团的向量和社团相似度矩阵,在图自编码器的目标函数中加了社团结构项;另一方面,利用第一个工作中提出的采样算子从自编码器输出的网络嵌入表示中提取社团表示,构成了进化优化的初始种群。上述两者结合实现了交替优化的网络嵌入学习算法。实验结果表明,我们提出的方法与经典的网络嵌入方法相比在基于网络嵌入的节点分类任务上表现良好。

关键词： 股票市场   已实现波动率跳跃   轮廓系数   网络动态演化   社团检测  

摘要： 随着世界经济的快速发展,经济全球化的趋势已势不可挡。各行业之间的发展也是环环相扣紧密相连。但我国股票市场发展并不完善,某一行业的突发事件,可能会影响多个行业的股票价格。为了帮助消费者更好地了解股票之间的相关关系以及及时掌握股票市场变化情况,本文以上证380成分股2018年5月2日至2020年4月17日股票价格为研究对象,利用R软件,通过已实现波动率理论和Min RV统计量提取已实现波动率中的跳跃,利用复杂网络技术建立已实现波动跳跃动态网络,并且对所构建的动态网络进行分析。首先,本文提出了一种基于局部随机游走距离轮廓系数的网络社团检测算法(SIL算法),并给出一个新的定量函数平均轮廓来评估质量网络社团结构。通过一些具有代表性的真实世界网络和计算机生成网络(GN网络和LFR网络)来测试该算法的准确性和效率。实验结果表明,与FG、LE、FP算法相比,SIL算法可以更有效地检测这些网络的真实社团结构。其次,本文基于已实现波动率及已实现波动率跳跃相关理论提取上证380成分股的已实现波动率,对已实现波动率跳跃构建股票动态网络。接着,通过上述跳跃动态网络的统计特征(最短路径长度、聚类系数、网络异质性、度分布、无标度特性及小世界特性),分析跳跃动态网络统计特征的动态演化,并且通过中心性指标识别出演化过程的关键节点。最后,使用社团检测算法对网络进行社团结构划分,通过与其它三种社团检测算法划分结果的模块度进行比较,本文所提出的算法(SIL算法)的模块度值最大。社团划分结果表明,跳跃动态网络中的社团在演化过程中是以行业划分。通过对股票跳跃动态网络重要节点挖掘发现制造业在股票市场占核心地位,金融业、媒体行业、高新技术行业对其它行业也具有较大影响力;对股票跳跃动态网络社团结构划分结果分析得到制造业内部,制造业、房地产业和采矿业之间存在密切联系。因此,投资者想要规避风险,就要做到“不把鸡蛋放在同一个篮子里”。

关键词： 复杂网络理论   超像素分割   社团检测   图像分割   度分布   目标检测  

摘要： 图像分割和目标检测一直是图像分析与计算机视觉领域的重点研究课题。随着近几十年来复杂网络理论的快速发展,将复杂网络理论应用到图像分析与计算机视觉领域成为研究人员关注的问题之一。本文以复杂网络理论中的社团检测和节点度分布理论为中心,对图像网络的构建、图像分割和视频中运动目标检测算法进行了研究。具体研究内容如下。（1）提出了一种基于局部网络模块度增量的超像素分割算法（LocalNet）。以像素点颜色相似性建立图像的邻接加权网络,以模块度增量作为判断准则,对邻接网络进行社团划分,完成图像的超像素分割。该算法克服了经典的SLIC超像素分割算法分割精度不足,易出现欠分割的缺点。同时应用超像素分割算法对图像进行分割,以超像素区域为单位作为网络节点,构建图像网络结构。与以像素点为节点构建图像网络相比,可以提高图像处理的效率。实验结果表明LocalNet算法与SLIC及其改进算法VASLIC和MMTDSLIC相比,具有更高的分割精度。（2）提出了一种结合局部度中心性的图像分割算法（LDCS）。对图像应用LocalNet算法进行超像素分割,以超像素区域为单位作为网络节点,区域间的颜色、纹理相似性作为连边权值,构建图像邻接加权网络结构,结合局部度中心性,计算图像网络的局部度中心节点作为图像网络社团的中心,进行网络的社团划分,完成图像分割。实验表明该算法的图像分割精度高于应用复杂网络理论进行图像分割的框架算法GFCNIS。（3）提出了一种基于图像网络节点度变化量的运动目标检测算法（IN-MOD）。对视频中每帧图像应用LocalNet算法进行超像素分割,以区域颜色、纹理相似性建立图像的邻接加权网络结构,按照时间顺序建立视频网络节点的时间序列,寻找每帧图像网络节点度变化节点作为候选运动目标,应用本文LDCS图像分割算法以及K-means聚类算法对检测出的运动目标候选区域进行修正。实验结果表明,本文IN-MOD算法在检测运动目标发生镜头抖动、光照变化等特殊情况时,具有较好的检测效果。

关键词： 隐藏社团结构   社团检测   HICODE   模块度   理论研究  

摘要： 在现实世界中,存在着各式各样的系统,这些系统往往可以抽象成图论中的网络。从网络中寻找到有价值的社团信息是重要且有意义的。近几十年来,社团检测在社会学、生物学、流行性疾病学等研究中被广泛研究并得到了快速的发展,出现了许多揭示网络结构算法。这些方法大多数用于不重叠或重叠的社团结构,或从全局社团结构转换为局部社团结构。2015年,何琨等人提出了一种新的图论概念:“隐藏社团结构”。如果一个社团的大部分成员属于更强大的社团,这个社团被称为隐藏社团。一个社团的强大可以通过一些社团度量指标如模块度来定义。他们还提出了一种既能探测显层结构也能探测隐藏结构的框架HICODE(Hidden community detection)。但是他们仅通过实验对HICODE的有效性进行了说明,并没有从理论上去证明。本研究对隐藏的社团结构进行了全面而系统的理论分析;提出了多层随机块模型作为现实网络的抽象,其中每一层都是网络节点的一组不重叠的社团划分(最强的一层是显层,其他所有层都称为隐藏层);同时,从理论方面证明了与等效随机噪音相比,隐藏结构噪音会使得显层划分的模块度更低,并且带隐藏结构噪音的网络会呈现双峰的结构。这解释了为什么隐藏结构噪音会导致传统社团检测算法检测显层更加困难;另外在两层,三层,多层随机块模型上证明了对目标层外某层和对目标层外所有层使用弱化方法(移除内边、削弱内边、削弱权重)后,目标层的模块度上升。这展现了HICODE在带隐藏结构噪音的随机块模型上的有效性,体现了HICODE不仅可以探测隐藏结构,同时可以提高显层的探测准确度;最后在两层和三层随机块模型上进行了HICODE的仿真,再次验证了HICODE算法的有效性。