论文部分内容阅读
随着互联网技术的迅猛发展,以及网络应用软件逐渐的人性化与社会化,推动了人与人之间的交流和沟通,加速了社会网络的繁荣和进步。社会网络中蕴含着丰富的用户信息及用户间互相作用的链接关系信息。通常可以用图表示的多关系数据集来代表社会网络,图上的节点表示对象,边表示对象之间相互作用的关系。在过去的几十年间,社会网络的研究受到越来越多的关注。对于社会网络的分析与研究,深入挖掘网络的结构特性、群体行为和传播机理等对于进一步了解网络系统具有现实意义。当前,社会网络的研究中备受关注的焦点问题有如何发现网络的社区结构以及如何合理有效地评价网络中用户的重要性。社区是社会网络的最重要的一个属性,它是具有共同性质的对象的集合,其中集合与集合之间的对象的连接比较稀疏,而集合内的对象的连接非常稠密。社区发现问题就是识别出网络中关系密切的节点的集合,可以理解为子图识别问题,它是挖掘社会网络中潜在的结构的一个重要任务,已经引起了越来越多的数据挖掘领域的研究者的广泛关注。此外,在社会网络分析中另外一个重要的研究方向就是挖掘网络中重要的节点,合理地评估节点的影响力,这对于社会管理、商业营销等方面都有着广泛的应用和意义。本论文在对传统和现代的社区发现算法进行研究和分析的基础上,提出了一种新的基于代表点的社区发现算法——RCD算法。RCD算法采用CURE聚类算法的思想,提出了使用多个代表点来代表一个社区,并通过离心率来选取中心点,然后根据节点的相似性来选取代表点,最后根据社区的相似性依次合并相似度最大的两个社区,直到达到期望的社区个数,最终得到了局部联系紧密的社区结构。其中计算节点的相似性时,针对Jaccard相似性的局限性给出了修正,使得相似度的计算更加合理。算法通过在karate数据集、AmericanCollege football数据集和采集整理的DBLP中ACM SIGMOD会议的作者协作关系数据集上进行实验,并与其它几种算法进行了比较,验证了RCD算法的准确性和有效性。另外,本论文还在社区发现的基础上提出了基于节点连接模式的影响力评定方法,该方法不同于传统的节点影响力评定方法,传统的方法大多都是从网络整体的拓扑结构出发,而基于节点连接模式的影响力评定方法是从网络的局部社区信息的思想出发。将社区内的节点的连接模式分为两类,对于与不同的社区都有连接的节点认为其重要性比较高,因为它们相当于社区之间的桥梁的作用,对于社区之间的通信起到重要的意义。算法在三个数据集上进行了验证,并与度中心性和介数中心性进行了斯皮尔曼一致性对比分析,验证了基于节点连接模式的影响力评定方法的可靠性和合理性。总之,本论文既提高了社会网络的社区发现的质量,也使得网络中节点的影响力评定更有效。今后的研究重点主要关注于在提高社区发现算法的效率的同时也保证算法的精度,以适应大规模的网络;对于节点影响力的评定方面,要考虑节点包含的更多的信息,使得评定方法更合理。