论文部分内容阅读
随着WEB2.0概念的不断深入,大量用户交互式社会媒体如微博,Facebook、twitter、论坛,社交网络,社会新闻,维基等不断涌现,产生了基于这些共享社会媒体平台的新型社会网络。社区发现是复杂网络研究的前提和重要任务。大量实证研究表明在复杂网络中普遍存在社区结构。社区结构内部节点之间联系紧密,而与外部节点联系稀疏。在社会网络中,社区结构信息能够帮助社会学者更好地理解社会群体;帮助商家发现潜在客户群体,进行个性化群体推荐,从而带来巨大的商业价值。因此,从复杂的社会网络中发现社区具有十分重大的理论和实际意义。社区发现通常可以从两方面出发:网络结构和节点属性。本文提出了一种社会网络社区发现的新算法(简称SARIE算法)。这个算法既考虑了网络结构的宏观性又考虑了其节点属性的微观性。通过基于网络结构的随机游走得到一系列的节点路径,每一条节点路径被当做一个可能的社区结构(本文称之为候选社区)。通过考虑节点属性信息熵来获得每一个候选社区的信息熵,根据信息熵阈值条件从候选社区中筛选出优质社区结构。优质社区须满足的条件是:社区结构中至少存在一个这样的属性,它的值对该社区的大部分成员都是相同的。一个属性的属性值所呈现出来的多样性由属性信息熵来度量,而社区信息熵则定义为该社区的最小属性信息熵。筛选优质社区就是筛选出社区信息熵不大于信息熵阈值的社区结构。算法的最后一步是合并相似社区。本文通过实验验证了SARIE算法的优越性和稳定性。采用常用的准确率和召回率的调和平均分数F1作为评价算法的指标。在Facebook数据集上得到的F1分数为0.656,与之前在同样的数据集上进行社区发现得到的F1分数最好的结果0.462相比,SARIE算法性能提高了41.99%。最后通过重复实验验证了其稳定性。SARIE算法十分简单,而且可以很容易地被并行化,因此能够应用于规模较大的社会网络;此外,SARIE算法能够发现重叠社区,同时支持网络节点多属性值的情况。算法最终不仅能够得到社区结构,同时给出了社区标签,有利于结果的直接应用。