基于模块性指标的动态网络社群结构探测方法

针对节点增加的动态网络,提出一种对应的动态网络社群结构探测算法CD(Community Structure Detection Algorithm for Dynamic Networks).CDD算法依据节点加入引起模块性指标变化的情况,对网络节点进行社群划分, 从而可以发现网络社群结构随时间的动态变化过程.利用计算机生成数据、Ucinet和Pajek提供的有关网络数据,通过社群结构探测试验表明, CDD算法不但可以对动态网络的社群结构变化进行探测,同样也可以实现静态网络的社群结构探测; 与N-G算法和A-N算法等社群结构探测算法相比, 算法的速度快, 所获得的模块性指标也基本相当.     

一种求解多维背包问题的小世界算法

针对遗传算法求解复杂组合优化问题时出现早熟收敛和种群多样性丧失等问题,提出了一种解决多维背包问题的二进制编码小世界算法(BSWA).BSWA算法依据社会学中的小世界现象搜索机理,采用类似遗传变异操作的局部搜索,而非遗传算法中的交叉操作.针对多维背包问题的多约束性,BSWA算法还按照价值资源比大小对不可行解进行贪婪修正,以保证求解的正确性.与遗传算法相比,BSWA可以在一定程度上克服早熟收敛,在保持种群多样性和求解精度方面均体现出较大的优势,具有解决复杂组合优化问题的潜力.对55个标准的多约束0-1背包问题进行了50次随机实验,结果表明,BSWA算法对于其中72.73%的问题可以次次获得最优解,对于其他不能次次求解到最优解的问题,也可以获得非常接近全局最优解的满意解.     

用于社群结构探测的小世界特征遗传算法

针对网络社群结构探测问题,探讨一种小世界特征遗传算法.受小世界现象搜索机理和网络结构特征启发,构造一种社群结构局部搜索算子;进而将该算子引入遗传算法基本框架,提出一种小世界特征遗传算法.典型网络的社群结构探测的结果表明,与Girvan-Newman算法和模拟退火算法相比,小世界特征遗传算法探测到的社群结构具有更大的模块性值,从而证明该算法是可用且有效的.     

基于先验知识与模块性的网络社区结构探测算法

在分析模块性指标和Newman有关网络社区结构探测算法的基础上，提出了一种基于先验知识与模块性的社区结构探测算法．利用节点度等社会网络结构先验知识，获得一个社区结构的基本划分，然后进行社区的合并，以此获得一个清晰的社区结构．经计算机模拟网络、Ucinet软件网络和中国农民工社会网络的社区结构探测，结果表明所提算法比Newman的迭代次数减少近50％，并且可以获得更好的模块性指标．     

“自底向上”合并社群结构探测策略中的顺序效应

基于模块性"自底向上"合并社群结构探测策略是目前复杂网络研究的热点问题之一,但是在依据模块性值变化对相应社群对进行合并时,往往出现顺序效应,即同一模块性值变化对应的社群合并可能不惟一,从而导致合并顺序不同而影响社群结构的最终探测结果。首先总结"自底向上"合并社群结构探测策略的一般算法框架,然后基于标准Ucinet和Pajek网络的社群结构探测结果,揭示Newman等提出的社群结构探测算法存在顺序效应,接着依据网络社群结构和社群密度的定义,提出用于克服顺序效应的基于社群密度的改进社群结构探测策略;最后,通过标准Ucinet和Pajek网络的社群结构探测结果,验证算法的有效性。