利用改进遗传算法进行复杂网络社团发现.pdfVIP

第３４卷第 １１期　 　 　 　 　 　 　 　 　 　 　 哈　 尔　 滨　 工　 程　 大　 学　 学　 报　 　 　 　 　 　 　 　 　 　 Ｖｏｌ．３４ №．１１ ２０１３年１１月　 　 　 　 　 　 　 　 　 　 Ｊｏｕｒｎａｌ ｏｆ Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ 　 　 　 　 　 　 　 　 　 　 　 Ｎｏｖ．２０１３ 利用改进遗传算法进行复杂网络社团发现 邓琨，张健沛，杨静 （哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨１５０００１） 摘　 要：针对使用遗传算法进行复杂网络社团发现时，存在较强随机性以及容易陷入局部最优解的缺陷，提出一种基于 遗传框架的复杂网络社团发现新方法．其通过一次迭代标签传播方法进行种群初始化，针对字符串表示法交叉困难的特 点提出了统一标签交叉策略，并采用有指向性的变异策略解决遗传算法随机变异的缺陷问题． 实验结果表明：对典型的 人工生成网络结构和真实网络结构，该方法能够较准确地发现社团结构；与经典算法进行比较，该方法具有较高的社团 发现精度且收敛速度较快． 关键词：复杂网络；社团发现；遗传算法；统一标签交叉策略；指向性变异策略 ｄｏｉ：１０．３９６９／ ｊ．ｉｓｓｎ．１００６⁃７０４３．２０１３０３００５ 网络出版地址：ｈｔｔｐ：／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ ｋｃｍｓ／ ｄｅｔａｉｌ／ ２３．１３９０．Ｕ０８４１．０１２．ｈｔｍｌ 中图分类号：　 文献标志码：Ａ　 文章编号：１００６⁃７０４３（２０１３）１１⁃１４３８⁃０７ Ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｕｓｉｎｇ ａｎ ｉｍｐｒｏｖｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ＤＥＮＧ Ｋｕｎ，ＺＨＡＮＧＪｉａｎｐｅｉ，ＹＡＮＧＪｉｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｒｂｉｎ １５０００１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｇａｉｎｓｔ ｔｈｅ ｄｅｆｅｃｔｓ ｏｆ ｓｔｒｏｎｇｅｒ ｒａｎｄｏｍｎｅｓｓ ａｎｄ ｌｏｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｗｈｅｎ ｔｈｅ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓｗａｓｍａｄｅｕｓｉｎｇｔｈｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，ａｎｅｗ ｍｅｔｈｏｄｏｆ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎｉｎｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｗａｓ ｐｒｅｓｅｎｔｅｄ ｕｓｉｎｇ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｓｔｒｕｃｔｕｒｅ． Ｔｈｅ ｓｉｎｇｌｅ⁃ｉｔｅｒａｔｉｏｎ ｌａｂｅｌ ｐｒｏｐａｇａｔｉｏｎ ｍｅｔｈｏｄ ｗａｓ ｕｔｉｌｉｚｅｄ ｔｏ ｍａｋｅ ｐｏｐｕｌａｔｉｏｎ ｉｎｉｔｉａｌｉｚｉｎｇ，ａ ｓｔｒａｔｅｇｙ ｏｆ ｕｎｉｆｉｅｄ ｌａｂｅｌ ｃｒｏｓｓｏｖｅｒ ａｇａｉｎｓｔ ｃｒｏｓｓｉｎｇ ｄｉｆｆｉｃｕｌｔｙ ｏｆ ｓｔｒｉｎｇ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｗａｓ ｐｒｏｐｏｓｅｄ，ａｎｄ ｔｈｅ ｄｉｒｅｃｔｉｏｎａｌ ｍｕｔａｔｉｏｎ ｓｔｒａｔｅｇｙ ｗａｓ ａｄｏｐｔｅｄ ｔｏ ｓｏｌｖｅ ｔｈｅ ｄｅｆｅｃｔｓ ｏｆ ｒａｎｄｏｍ ｍｕｔａｔｉｏｎ ｉｎ ｔｈｅ ｇｅ⁃ ｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｆｏｒ ｔｈｅ ｔｙｐｉｃａｌ ｃｏｍｐｕｔｅｒ⁃ｇｅｎｅｒａｔｅｄ ｎｅｔｗｏｒｋ ｓｔｒｕｃｔｕｒｅ ａｎｄ ｒｅａｌ⁃ ｗｏｒｌｄ ｎｅｔｗｏｒｋ ｓｔｒｕｃｔｕｒｅ，ｔｈｅ ｍｅｔｈｏｄ ｃａｎ ｄｅｔｅｃｔ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｍｏｒｅ ａｃｃｕｒａｔｅｌｙ． Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｃｌａｓｓｉｃａｌ ａｌｇｏｒｉｔｈｍｓ，ｉｔ ｈａｓ ａ ｈｉｇｈｅｒ ｐｒｅｃｉｓｉｏｎ ｏｆ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ａｎｄ ａ ｆａｓｔｅｒ ｃｏｎｖｅｒｇｅｎｃｅ ｓｐｅｅｄ． Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ；ｃｏｍｍｕｎｉｔ