论文部分内容阅读
复杂网络社区是由一组网络节点构成的集合,社区内部节点连接紧密,社区间节点连接稀疏。社区结构作为复杂网络的重要结构特征,对认识网络功能、研究网络拓扑结构、揭示网络中存在的规律、预测网络演化有重要意义。复杂网络社区结构检测已经应用于社会网络分析、恐怖组织识别、生物网络分析、Web挖掘、Web文档聚类、搜索引擎等方面。社区结构检测已经成为多学科交叉领域研究热点。本文从复杂网络的分形特性、启发式优化、多尺度社区三个方面对复杂网络社区结构检测开展研究工作。具体研究内容如下:1、提出基于分形聚类的社区结构检测算法(FCUC)。基于分形聚类的社区结构检测算法,通过盒子覆盖法实现对网络节点的聚类。将网络用若干盒子覆盖,盒子内节点形成一个簇,每个簇重整为一个节点,形成一个新的网络。重整过程中,对两个簇之间边的权重进行叠加,形成新网络中两个节点之间边的权重。在新网络中边的权重体现了两个节点连接强度。在新网络上继续使用盒子覆盖法进行覆盖和重整,不断进行迭代,直至网络只有一个节点,聚类过程结束。聚类过程形成的聚类层级结构称为分形树,分形树在一定程度上体现了复杂网络的演进过程。最后通过最大化社区评价指标方式对分形树进行分割,得到复杂网络社区结构。针对社区内部连接紧密的特点,为增强盒子内节点连接强度,提出了两阶段盒子覆盖法用于节点聚类。2、提出启发式人工蜂群社区结构检测算法(HABC)。针对社区结构检测问题,HABC算法在雇佣蜂、跟随蜂、侦查蜂搜索过程中引入启发函数,将人工蜂群算法搜索过程由随机搜索变为启发式搜索。启发函数定义为节点与社区之间凝聚概率,对蜜源的搜索过程变为将一个节点放入与节点相邻社区的过程,蜜蜂会选择一个与当前节点凝聚概率最高的社区,将节点放入该社区。算法中蜜源代表一个社区结构检测结果,好的蜜源对检测结果有较大的影响。在蜜源创建时,将所有完全子图从网络中筛选出来,同一完全子图中节点指定相同的社区标识符,从而使得蜜源具有简单的社区结构有助于搜索的开展。实验表明启发式人工蜂群社区结构检测算法能够有效地检测社区结构。3、提出谱分析与遗传算法相结合的多尺度社区检测算法(HGASA)。谱分析与遗传算法相结合的多尺度社区检测算法分为两个阶段:第一阶段,基于复杂网络的特征谱与网络拓扑结构密切相关的特性,HGASA算法通过对拉普拉斯矩阵特征间隙的分析得出复杂网络的多尺度特征,以及不同尺度下社区的数量;第二阶段,结合复杂网络多尺度社区结构信息,使用遗传算法进行社区结构检测。遗传算法交叉操作可以保证个体进化,为使网络中具有较强内部连接部分能交叉到新个体中,在算法中提出合并单路交叉操作,将一个完整社区交叉操作给新个体。变异操作中引入基于网络动力学的启发函数指导个体变异操作,并且证明遗传算法目标函数与启发函数之间存在单调关系。本文基于分形特性、启发式优化、多尺度社区结构,对复杂网络社区结构检测问题进行研究,具有一定的理论和现实意义。