基于中心团的重叠社区检测算法

社区检测已经成为了了解复杂网络结构和网络动态的一个重要途径。针对传统的节点聚类和链接聚类在发现重叠社区方面存在的两种固有缺陷,即参数依赖和结果不稳定,文中提出了一种基于中心团的局部扩展改进算法CLEM,用于检测重叠社区。该算法通过选取中心团为核心种子,并在种子扩展过程中惩罚被多次删除的节点,改善所得结果的稳定性;通过选取不依赖参数的适应度函数,改进其迭代计算过程,避免了适应度函数的参数限制,并降低了计算复杂度。在合成网络和现实网络上测试的结果表明,与已有算法相比,所提算法在计算时间和准确度上均有很好的表现。     

智能电网中基于极大团的社团结构挖掘算法

针对智能电网落后的分区方式无法适应日益复杂的运行状态和无法及时排查故障的问题,提出了一种基于极大团的智能电网社团结构挖掘算法(MCBCA).首先,搜索网络中的低阶极大团,通过合并矩阵将其合并得到网络中极大团;然后,定义了极大团相似度,确定了合并极大团与生成候选子图的标准,进行初步社团挖掘;最后,对网络中的孤立节点进行隶...     

一种基于个体中心论的局部优化社区发现算法

随着社会网络网站的流行,虚拟社会网络中的社区发现成为一个热门研究领域.针对虚拟网络中总是以一个或多个个体为中心特点,提出了一个针对大规模社区网络的局部优化社区发现的算法,在一定程度上弥补了传统算法无法适应大规模网络的不足.实验表明与我们直观想象不同,虚拟网络中那些度最大的点并不一定适合于作为社区中心.     

一种基于极大团的关键时间段挖掘方法

针对带有时间属性的海量事务处理问题,提出了一种求最大相关性的最小时间区间(关键时间段KTI)的算法。通过利用极大团把海量的数据项进行有效的划分,降低了后续数据挖掘和决策选择的复杂度。针对特定的含有时间参量的极大团,通过寻找关键时间段(KTI),提高了决策的准确度,同时可以减小分析数据的规模,降低对计算资源的需求。假设事务中各项出现的事件具有相同的概率分布,得到了一种寻找关键时间段(KTI)的算法。从理论上证明了算法的正确性,并对其进行了复杂度分析,通过实际数据验证了算法的可行性。     

基于FP-tree的极大超团模式挖掘算法

超团模式挖掘是数据挖掘领域新的研究内容之一,极大超团模式挖掘是超团模式挖掘的扩展,在分析已有算法的基础上,提出了一种新的挖掘极大超团模式的算法。新算法在保持已有算法中有效剪枝策的基础上,针对基于FP-tree挖掘极大超团模式的特点,算法中增加了新的剪枝策略,并引入了极大超团模式树,用于保存极大超团模式和进行极大超团模式检测,实验表明新算法的正确性和有效性。     

可信关联规则及其基于极大团的挖掘算法

目前的关联规则挖掘算法主要依靠基于支持度的剪切策略来减小组合搜索空间.如果挖掘潜在的令人感兴趣的低支持度模式,这种策略并非有效.为此,提出一种新的关联模式—可信关联规则(credible association rule,简称CAR),规则中每个项目的支持度处于同一数量级,规则的置信度直接反映其可信程度,从而可以不必再考虑传统的支持度.同时,提出MaxcliqueMining算法,该算法采用邻接矩阵产生2-项可信集,进而利用极大团思想产生所有可信关联规则提出并证明了几个相关命题以说明这种规则的特点及算法的可行性和有效性.在告警数据集及Pumsb数据集上的实验表明,该算法挖掘CAR具有较高的效率和准确性.     

基于“次中心”的社区结构探寻算法

当前社区结构探测算法在寻求社区结构划分正确性的同时,算法效率较低。为此,提出一种在算法正确性和算法效率两个方面能取得较好均衡的社区结构探寻算法CoreScan。该算法寻找节点集合中一类称之为“次中心”的特殊节点,再将其作为聚类中心,然后通过D模块度来发现社区结构。理论分析表明,该算法能正确识别Fortunato提出的一类特殊社区结构,且算法效率可达O(n*kmax),其中n是节点数量,kmax是“次中心”最大数量。最后通过多项实验证明,CoreScan算法能够在效率和正确性上取得较好的均衡,适合于在大规模节点集合中进行快速社区结构探寻。     

基于极大团和FP-Tree的挖掘关联规则的改进算法

融合了关联规则挖掘的FP-Tree算法和图论的极大团理论的优势,做了以下主要工作:(1) 提出了用邻接矩阵的产生频繁2-项集的改进方法;(2) 提出了极大有序频繁集的概念,证明了Head关系的等价性、划分定理、局部复杂性定理和归并收敛值域定理;(3) 提出并实现了基于极大团划分的MaxCFPTree算法,扫描时间复杂性小于O(n²);(4) 做了相关实验,以验证算法的正确性.新方法缓解了项目数量巨大而内存不足的矛盾,提高了系统效率和伸缩性.     

CPM-MCHM:一种基于极大团和哈希表的空间并置模式挖掘算法

空间并置(co-location)模式挖掘是指在大量的空间数据中发现一组空间特征的子集,这些特征的实例在地理空间中频繁并置出现.传统的空间并置模式挖掘算法通常采用逐阶递增的挖掘框架,从低阶模式开始生成候选模式并计算其参与度(空间并置模式的频繁性度量指标).虽然这种挖掘框架可以得到正确和完整的结果,但是带来的时间和空间开...     

基于共享邻居数的社团结构发现算法

为了快速准确地找到复杂网络的社团结构,提出一种基于共享邻居数和局部模块度的社团结构发现算法。该方法通过不断寻找节点之间的共享邻居数找出与社团连接性最强的节点,并以局部模块度为衡量标准,判断是否将该节点加入到社团中。对3个典型复杂网络的划分结果表明,该算法是可行和有效的。     

基于组合模型的局部搜索弱社团结构发现算法

针对复杂网络社团结构发现算法中全局模块度存在的分辨率缺陷问题,即不能发现很多实际存在的小社团,甚至发现的社团不满足普通意义上的社团定义,给出一种新型的多目标整数规划模型。结合弱社团定义、局部适应度和全局模块度标准,提出一种高效的启发式算法,发现网络的层次重叠社团。实验结果表明,该算法克服全局模块度的缺陷,能充分挖掘出小社团,具有较高的效率。     

模块度增量与局部模块度引导下的社区发现算法

社区结构是复杂网络的重要特性之一,基于层次聚类的社区发现算法很好地利用了模块度来挖掘网络中的社区结构,但其局限性也导致算法对社区结构复杂的网络划分不够准确、无法发现小于一定规模的社区。在层次聚类的基础上,提出引入局部模块度来弥补模块度在划分社区时的不足,避免可能出现的划分不合理情况。通过真实数据集和人工网络进行了验证,实验结果证明,该算法具有可行性与有效性。     

网络社区发现的粒子群优化算法

从优化模块度的角度出发,提出了一种基于粒子群优化的网络社区发现的粒子群优化算法（CDPSO）;该算法根据网络连接数据的特点给出一种新的粒子编码方法,有效地避免非法粒子的产生,一定程度上缓解了基于二值编码的迭代二划分策略所遭遇的局部最优划分问题,并改进了传统离散粒子群优化（PSO）的粒子位置调整策略,使算法收敛速度更快.实验结果表明,CDPSO能够在无先验信息的条件下快速有效地揭示网络内在的社区结构.     

基于粒子群优化的复杂网络社区挖掘

为解决复杂网络社区结构挖掘的优化问题,根据复杂网络拓扑结构的先验知识,提出一种基于离散粒子群优化的社区结构挖掘算法。将粒子的位置和速度定义在离散环境下,设计粒子的更新规则,在不需要事先指定社区个数的前提下自动判断网络的最佳社区个数,给出局部搜索算子,该算子可以帮助算法跳出局部最优解,提高算法的收敛速度和全局寻优能力。实验结果表明,与iMeme-net算法相比,该算法能够准确地挖掘出复杂网络中隐藏的社区结构,且执行速度较快。     

一种新的评价社区结构的模块度研究

指出Newman和Girvan提出的模块度概念(Physical Review E, 2004, E69)不适用于社区大小差异较大的情形。为克服这一缺陷,提出与社区大小无关的连接密度和内聚系数概念,在此基础上,构造一种新的模块度。理论和实践证明,该模块度适用于社区大小相似以及社区大小差异较大的情形。     

改进的CNM算法对加权网络社团结构的划分

为了对可以反映网络结构局部重要性质的加权网络进行社团结构划分,延续广泛应用的社团结构分级聚类方法,改进Newman贪婪算法（CNM算法）。算法设计中引入点权和边权,并重新定义新的Q函数计算社团模块度,通过寻找Q函数峰值确定社团划分的最终结果。另外以股票价格波动相关性为加权边建立的加权网络为例进行算法检验,社团划分的结果验证了改进的CNM算法的有效性。与改进的GN算法、极值优化算法等划分效果进行比较分析后发现,改进算法在划分准确性及算法复杂度等方面都有明显的优势。