论文部分内容阅读
自然世界里存在着“物以类聚,人以群分”的现象,在对复杂网络的研究中发现实际网络中都存在着这个现象,称之为社区结构:即可以将网络划分为若干个社区,社区内部的节点间连接紧密而社区之间的连接较为稀疏。挖掘复杂网络的社区结构具有重要的研究意义和广泛的应用前景,不仅可以帮助我们理解网络的结构,了解网络的特性,还可以有助于分析网络的形成以及预测网络的发展。 目前已经有很多成熟的社区挖掘算法,例如GN算法、Newman快速算法等。也有人加入了节点的属性相似度进行社区挖掘,例如SA-Cluster算法。但考虑节点间地理距离的社区发现算法还较少。基于Tobler第一定律,空间上越接近的事物越相关,因此本文认为节点间的紧密度不仅仅与拓扑连接有关,同时也与节点之间的地理距离密切相关,在对空间网络进行社区挖掘时需要同时考虑这两种紧密性。 基于这个想法,本文提出将节点的地理位置考虑到社区挖掘过程中,认为连接的强度与节点间的地理距离有关,将距离n次幂的倒数作为边权,修改了衡量社区挖掘结果好坏的模块度函数。同时,本文基于复杂网络模块度的概念提出了一种用于评价空间点集聚类特征的集聚度值。然后修改CNM算法,用修改后的模块度函数作为聚类的准则函数,从而对空间网络进行社区挖掘。之后,本文采用国内民航航空网络和BrightKite社交网络作为实例研究,用修改后的算法分别对进行了社区挖掘与分析。由于地理约束的作用,挖掘到的社区数目远远多于原算法,且这些社区的空间分布具有一定的地域性。并且本文用原模块度函数和集聚度函数分别对得到的社区结构进行了拓扑连接模块度和节点的空间集聚度进行评价,发现该算法能够较好的综合考虑到地理空间和拓扑空间节点间的紧密关系。最后,本文分析了BrightKite数据中的一位活跃用户在不同的时间段他及其好友处于不同的地理位置,社交圈子随之发生的改变。 研究表明,该算法能够很好的识别连接紧密且空间上接近的社区结构,对空间网络的社区挖掘具有重要的应用价值,更加有助于分析网络的拓扑结构和节点的空间分布特征之间的联系。