基于加权边介数的Web社区发现方法

Web是一个典型的复杂网络。Web在发展的过程中存在着大量的社区,这些社区是Web组织中非常重要的信息。Web社区提供了特定主题下的相关资源,可以为用户提供有价值的、可靠的、及时的信息。Web社区代表了Web中的社会活动,对社区的深入研究可以了解Web中知识信息及其组织结构的发展状况。发现Web社区对提高用户查询效率及实现网页分类有着重要意义。 本文对已有的基于链接结构的Web社区发现算法进行了分类,并通过对三种典型的Web社区发现技术的理论与实验分析发现已有算法发现的社区结果的网页之间链接不是很紧密,而且会出现一定的主题漂移现象。根据Web的复杂网络特征,本文提出了一种改进的发现特定主题Web社区的GN算法。该算法利用莱温斯坦距离衡量Web页面与查询主题及Web页面间的相似度。将网页的title与查询主题的相似性作为网页节点的权值,将有链接关系的两个网页的title之间的相似性作为这两个网页之间相连的边的权值。然后利用GN算法对网络拓扑图进行分割,根据分裂过程中是否产生新的连通分量来指导边介数的计算。改进的GN算法的复杂度明显降低。同时本文提出了社区密度和社区平均相似度的概念来衡量社区质量,并作为选择最接近主题社区的依据。为了评价改进的GN算法的性能,本文将该算法与基于链接分析的发现特定主题社区的主要算法HITS和最大流进行了比较。本文详细论述了实现平台系统的搭建,包括实验数据集的收取与处理、算法实现及社区结果的可视化。实验结果表明,改进的GN算法所发现的特定主题社区与HITS算法和最大流算法发现的社区比较,多数情况下主题相关度提高14%。