基于P4结构的社团挖掘方法

作     者：张献鹏 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：高琳

授予年度：2014年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：复杂网络 P4结构 社团挖掘 

摘      要：目前在社会学、生物学和计算机科学领域,人们通常将复杂的系统用网络来描述,因此对图进行社团挖掘是一项非常重要的工作。从概念上和实际操作中来讲,这项任务都是一项艰难的任务。从概念上来说,目前社团的定义非常的模糊,科学家们并没有给出具体的定义,同样不同社团之间的界限也很模糊。在实际中,算法要处理大量的数据来发现“较好的社团也是一件很困难的事情。另一个复杂的问题就是社团之间的可重叠性,因为节点是可能会属于多个社团。同一社团的成员之间拥有更多的连接,这是目前的大多数的方法所依据的假设。这就使得社团挖掘转化成了网络中稠密子图的挖掘。而且,这些方法还有一个问题就是,他们将网络中的每个节点仅仅分配给一个社团,这样的结果使的社团并不具备被可重叠性。本文提出了一个基于P4结构的社团挖掘方法,该方法引入了一个特殊结构P4进行社团挖掘。P4结构的引入使得该方法具有无参且无需任何先验知识的特点。又由于P4结构的稀疏特性,使得社团结构含有P4结构的概率极小。因此,可以通过判断一个节点是否与社团内部原有节点构成P4来判断该节点是否应该加入该社团。通过该方法获得的社团结构保证了一定的稠密性。为了验证方法的有效性,使用了空手道俱乐部网络和Newman人工网络进行了试验研究,均获得了正确的社团结构。另外将该方法应用在人类的PPI网络上面,与现有方法进行比较,结果显示该方法的F-mearsure得分要平均高于其他方法5%。通过本文方法挖掘的社团具有可重叠性,而该方法并不需要任何的参数输入,从而避免了因为参数的改变而影响整个结果。