论文部分内容阅读
网络技术的快速发展给人们带来大量的网络资源,如何从浩瀚的网络资源中快速有效的找到所需的资源成为当今学者研究的一个重要课题。学者们研究发现这些资源之间并不是毫无关联的,而是存在着某种联系,即网络中所呈现出的社区结构。由于社区结构是复杂网络的一个重要特性,所以研究社区结构不仅有利于人们更好的认识复杂网络,而且对解决现实世界中的疑难问题有重要的理论和现实意义。本文首先对复杂网络度量特性进行了分析,研究了复杂网络的几种典型网络模型,并对社会网络进行了简要描述。然后对现有网络社区划分算法进行了分析研究,发现有些算法在某些特定的网络中发现社区的准确度较高,但是这些算法执行时间复杂度也较高;有些算法对处理结构混乱的网络效果好,但是只适用于具有特定结构的网络。最后,本文以分析复杂网络动态结构为目的提出了两种算法,即在动态网络中发现非重叠社区的算法和发现重叠社区的算法。复杂网络的动态特性使得网络社区发现算法需要加入时间轴信息,以得到网络社区发现结果更加真实。本文首先提出了在动态网络中发现非重叠社区的算法,该算法是基于GN算法边介数的思想基础,同时在计算网络边介数的过程中考虑局部计算,在很大程度上改进了算法的时间复杂度。首先,算法对动态网络时间轴上的信息进行了整合,并根据社会学经验将历史信息进行了信息量衰减,使得到的网络数据信息更加接近于真实世界的数据信息。其次,根据网络中边介数最大的边是网络中关键边的特性,利用去除网络中边介数最大的边而得到不连通子图,这些不连通的子图成为了一个个的社区结构。然后,本文在3组数据集上进行了算法验证,并对结果进行了分析,发现算法得到的社区划分结果是比较正确的。最后,在不同数量级的数据集上,与Framework模型和FacetNet算法进行了时间复杂度的对比,发现本文算法在处理大数据集的能力上有明显优势。本文基于网络中存在一个节点可能会出现在多个社区的网络特征事实,提出了另一种动态网络中发现重叠社区的算法。该算法是在动态网络中发现非重叠社区算法的基础上,对网络结构特性进行了重新思考,利用复制网络中分割介数最大的节点而得到网络社区结构。算法步骤是在非重叠社区算法基础上加入复制分割介数最大的节点,以得到不连通子图进行社区发现。最后,在C-DBLP数据集和全球食品出口贸易数据集上对算法进行了验证分析。本文所提出的两个动态网络社区发现算法,利用了局部介数的思想,在算法时间复杂度上有了很大的改进,同时算法发现社区的准确度较高,值得推广和应用在现实世界中。