种子节点非重叠社团挖掘算法研究

ＳｔｕｄｙｏｎＣｏｍｍｕｎｉｔｙＭｉｎｉｎｇＡｌｇｏｒｉｔｈｍＢａｓｅｄｏｎＳｅｅｄＮｏｄｅｆｏｒＮｏｎＯｖｅｒｌａｐｐｉｎｇ

中文关键词:社团挖掘  种子节点  节点重要性综合评价指标  复杂网络  非重叠社团

英文关键词:ｃｏｍｍｕｎｉｔｙｍｉｎｉｎｇ  ｓｅｅｄｎｏｄｅ  ｃｏｍｐｒｅｈｅｎｓｉｖｅｅｖａｌｕａｔｉｎｇｉｎｄｅｘｆｏｒｎｏｄｅｉｍｐｏｒｔａｎｃｅ  ｃｏｍ－ ｐｌｅｘｎｅｔｗｏｒｋｓ  ｎｏｎｏｖｅｒｌａｐｐｉｎｇｃｏｍｍｕｎｉｔ ｙ

中文摘要:

      提出一种新型的种子节点社团挖掘算法，首先，利用主成分分析技术由单一性节点重 要性评价指标提取出综合性评价指标，挑选评价指标值最大的节点作为种子节点，对其进行广 度优先搜索，指标值大的节点不断地影响指标值小的节点，得到种子节点所在的社团结构。然 后，从已知社团结构外选取综合性评价指标值最大的节点重复上述过程，得到初始社团结构集 合。对于社团结构间存在重叠节点情况，根据重叠节点与两个社团间的连边数解决重叠节点的 归属问题，得到最终网络的社团结构。基准网络的实验结果表明，所提出的综合评价指标能更 好地表征节点的重要性，与谱方法社团挖掘实验结果相比，所提出的种子节点社团挖掘算法具 有较高性能。

英文摘要:

      Ａｎｏｖｅｌａｌｇｏｒｉｔｈｍ ｂａｓｅｄｏｎｓｅｅｄｎｏｄｅｆｏｒｃｏｍｍｕｎｉｔｙｍｉｎｉｎｇｉｓｐｒｏｐｏｓｅｄｉｎｔｈｉｓｐａｐｅｒ． Ｆｉｒｓｔｌｙ，ａｃｏｍｐｒｅｈｅｎｓｉｖｅｅｖａｌｕａｔｉｎｇｉｎｄｅｘｆｏｒｎｏｄｅｉｍｐｏｒｔａｎｃｅｉｓｅｘｔｒａｃｔｅｄｆｒｏｍｓｉｎｇｌｅｉｎｄｉｃａｔｏｒｓｂｙｕ－ ｓｉｎｇｐｒｉｎｃｉｐａｌｃｏｍｐｏｎｅｎｔａｎａｌｙｓｉｓ．Ｎｏｄｅｗｉｔｈｔｈｅｍａｘｉｍｕｍｉｎｄｅｘｖａｌｕｅｉｓｓｅｌｅｃｔｅｄａｓａｓｅｅｄｎｏｄｅａｎｄ ｂｒｅａｄｔｈ－ｆｉｒｓｔｓｅａｒｃｈｏｐｅｒａｔｉｏｎｆｏｒｓｅｅｄｎｏｄｅｉｓｅｘｅｃｕｔｅｄ．Ｎｏｄｅｓｗｉｔｈｇｒｅａｔｅｒｉｎｄｅｘｖａｌｕｅａｆｆｅｃｔｓｍａｌｌｅｒ ｎｏｄｅｓｇｒａｄｕａｌｌｙａｎｄｔｈｅｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｗｈｅｒｅｓｅｅｄｎｏｄｅｉｓｌｏｃａｔｅｄｉｓｇｏｔｔｅｎ．Ｔｈｅｎ，ｎｏｄｅｉｓｃｈｏｓｅｎ ｗｉｔｈｔｈｅｌａｒｇｅｓｔｉｎｄｅｘｖａｌｕｅｆｒｏｍｔｈｅｏｕｔｓｉｄｅｋｎｏｗｎｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ．Ｔｈｅａｂｏｖｅｐｒｏｃｅｓｓｉｓｒｅｐｅａｔｅｄ ａｎｄｔｈｅｉｎｉｔｉａｌｃｏｍｍｕｎｉｔｙｓｅｔｉｓｇｏｔｔｅｎ．Ｆｏｒｔｈｅｏｖｅｒｌａｐｐｉｎｇｎｏｄｅｓｂｅｔｗｅｅｎｃｏｍｍｕｎｉｔｉｅｓ，Ｏｖｅｒｌａｐｐｉｎｇ ｎｏｄｅｓａｎｄｔｈｅｎｕｍｂｅｒｏｆｅｄｇｅｓｂｅｔｗｅｅｎｔｗｏｃｏｍｍｕｎｉｔｉｅｓｉｓｕｓｅｄｔｏｓｏｌｖｅｔｈｅａｔｔｒｉｂｕｔｉｏｎｐｒｏｂｌｅｍ．Ｆｉｎａｌ－ ｌｙ，ｔｈｅｕｌｔｉｍａｔｅｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｏｆｔｈｅｅｎｔｉｒｅｎｅｔｗｏｒｋｉｓｅｓｔａｂｌｉｓｈｅｄ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｆｏｒ ｂｅｎｃｈｍａｒｋｎｅｔｗｏｒｋｓｓｈｏｗｔｈａｔｃｏｍｐｒｅｈｅｎｓｉｖｅｅｖａｌｕａｔｉｎｇｉｎｄｅｘｉｓｍｏｒｅｓｕｉｔａｂｌｅｆｏｒｎｏｄｅｉｍｐｏｒｔａｎｃｅ ｔｈａｎｓｉｎｇｌｅｏｎｅｓ．Ｃｏｍｐａｒｅｄｗｉｔｈｓｐｅｃｔｒａｌｍｅｔｈｏｄ，ｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅｐｒｅｓｅｎｔｅｄａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎ ｓｅｅｄｎｏｄｅｉｓｈｉｇｈｅｒ．