论文摘要
在自然界和人类社会中，复杂网络与复杂系统广泛存在，如蛋白质交互网络、人际关系网、科学家协作网络、交通网络、因特网等。复杂网络往往规模大，数量多，范围广，并且还处于动态演化中，这促使不同领域的学者们去研究它们，其理论研究和应用研究都非常富有吸引力和挑战性，亦有着广阔的应用前景。如今复杂网络的研究成果已经非常丰富了，科学家们还在不断地开发出新的研究方向和应用领域。本论文在阐述复杂网络基本理论及研究概况的基础上，对复杂网络的几类度量性质和拓扑性质进行了探讨，取得了一些研究成果。对度量性质的研究以电阻距离为基础，把电阻距离作为网络中两个节点之间的相似性度量，进行了一些应用方面的探索。由于所有研究都是在网络上进行的，不可避免地涉及到了网络的拓扑结构，因此，从另一个角度而言，本论文也对复杂网络拓扑性质进行了研究，比如社团结构、无标度特性等。具体而言，本论文的主要研究工作及贡献体现在以下几个方面：1.提出了一种度序列为等比数列的无标度网络模型。通过理论证明了它的无标度特性，同时也得到了它的幂指数。该网络模型的度序列为首项是一个正整数、公比q为大于1的正整数的等比数列，其长度为l。在这个模型中，度为k i的节点个数为bn-i+1，幂指数为logqb，这儿b也是大于1的正整数， n=l-1。等比数列可以用于确定网络的基本参数，如幂指数、最小度和节点数。分析发现，网络的拓扑结构随着度序列长度的变化而变化，但是其无标度特性始终不变。2.以复杂网络的视野对电阻距离这一特性进行了简单的综述，给出了普通网络与电网络的转化关系，讨论了它的各种计算方法、用途与性质，证明了电网络里有效电阻也是一种距离度量，并简短论述了它与随机游走之间的关系，介绍了电阻距离一个著名的性质。这个性质也是大部分相关应用的理论基础。应用前述电阻距离及其性质，利用电阻距离来度量数据对象之间的相似性，提出了一个新颖的谱聚类算法。分析了谱聚类的基本流程及一般原理，并探讨了几个常见的谱聚类算法的相似性度量，在此基础上把电阻距离引入谱聚类算法中。经过理论推导，证明了本算法可以完成各种不同的数据聚类任务。相关实验验证了本算法的有效性。3.首先设计了一种基于电阻距离的社团发现算法。根据网络的小世界效应和无标度特性可知，每个社团结构中都有一些度较大的中心节点。基于电阻距离的算法利用电阻距离和节点的度数共同来确定社团的中心节点，然后比较其他所有的节点与中心节点之间的电阻距离以确定所在聚类，这也是利用了电阻距离的度量性质。在第一种算法的基础上，又提出了一种改进的算法。这第二种算法初始阶段把所有的节点都设为“未访问”状态，然后搜索未访问的节点以寻找所谓的强结构子网，并标记它们为“已访问”。这种强结构子网一般是由一个度最大的中心节点及其大部分邻居组成。再根据某种准则把其他未访问的节点分派到不同的强结构里。最后对存在的强结构子网进行优化以确定最终的社团。相关实验验证了两种算法的稳定性、有效性和精确性。4.同样是利用电阻距离及其性质，完全以电阻距离的视野提出了一个新的中心性度量指标以评价节点在网络中的重要性。一个节点的电阻距离中心性被当作是这个节点与其他所有节点的电阻距离之和的倒数。这个电阻距离中心性实际上与信息中心性是一致的。另外，探讨了电阻距离中心性与几个经典的中心性度量指标的差异。为了评估所提中心性度量的精确性，利用一些人工或真实网络数据进行了测试。实验结果表明，电阻距离中心性指标的表现优秀，尤其是在正则图上电阻距离中心性很明显比其他的中心性度量指标要优异得多。