基于三元闭包和会员闭包的社区发现算法研究

摘要

随着网络的发展和人们沟通方式的扩展,社交网络影响了人们的生活,改变了人们传播与分享消息的方式,吸引了越来越多的人关注和研究社交网络.社交网络即社交网络服务,源自英文SNS(social network service)的翻译,社交网络有多种表现平台,比如QQ、微博、Facebook和微信.本文主要研究微博这一新兴的社交平台,研究微博的主要目的是搞清用户之间的种种关系.当代人一般认为,微博中存在5种关系即关注关系、提及关系、转发关系、评论关系以及好友关系.由于社交网络中人数众多,关系错综复杂,因而产生的社交数据和传统的数据相比具有数据量大、结构复杂、语义丰富等特点,针对这种情况,依据用户之间的关系,提出了一种基于三元闭包的社区划分算法.该算法首先设初始社区为空,在所有的顶点中,选择度最大的顶点作为初始顶点;然后求初始顶点与其邻接顶点的三元闭包数和顶点属于该社区的概率Ps,取它们最大的邻接顶点加入初始顶点所在社区,形成新的社区,继续迭代,当剩余的顶点很少时,可以使用会员闭包和三元闭包这种归集算法把剩余的顶点划分到不同的社区,直到把整个社区划分完毕;最后以图形这种直观、形象的方式把每一个社区表示出来.在该算法中,三元闭包数、顶点属于某社区的概率、扩张度的差是评估复杂网络中顶点划分的关键.该方法综合了顶点全局重要性的特点,即在复杂网络中,三元闭包数越大,它们处在一个社区的可能性就越大;顶点的会员闭包越大,该顶点就会越优先被划分;扩张度的差是确定第i个社区是否被划分完毕的关键.社交网络的研究不仅可以帮助人们了解网络结构、分析网络结构特性、探测分析网络的社团结构,而且还可以把虚拟世界中这种关系链接到现实世界中,即把虚拟关系转化成利润,为企业提供有价值的关系网络,从而挖掘出潜藏在社交网络背后的巨大的经济价值,具体体现在:1)帮助企业找到潜在的商机,比如分析某个用户的评论和发表内容,可知他的消费能力、喜好和最近的购买习惯,从而知道他购买自己产品的概率;2)危机预警,根据用户的消息内容可以知道他对自己产品的满意度;3)带动了消息的传播速度和广度.企业可以利用这一点,为自己的产品更好地做宣传.通过与宽吻海豚网和Zachary空手道俱乐部的社区网络作比较,证明了该算法的有效性和可行性.