论文部分内容阅读
由于21世纪的第二个十年将是实现人、机、物和信息等要素和谐共生的物联网和社会网络时代,许多国家都将面向网络化社会的研究提升到了国家战略层次,而在各种网络的实际应用中社区发现是一个不可逾越的步骤,所以深入展开网络社区发现研究具有十分重要的意义。拓扑势理论是一种新的社区发现理论。较之传统社区发现方法,基于该理论的社区发现方法具有多方面的优势。针对传统社区发现方法和拓扑势社区发现方法存在的不足,并以对拓扑势理论及其社区发现方法进行改进、完善和发展为主线,本文主要从四个方面展开研究。首先,证明了拓扑势熵最小值点存在性定理。网络中拓扑势熵最小值点的存在性是拓扑势理论及其方法进行社区发现的前提和基础,然而目前对其只限于有限的实证研究。该定理表明了拓扑势熵最小值点在千差万别的网络中存在的一般性,明确了基于拓扑势的网络社区发现方法的应用范围。其次,提出了基于拓扑势的重叠节点社区归属不确定性测度。目前许多社区发现方法为只允许一个节点只能属于一个社区的硬方法,缺乏现实合理性。事实上,众多网络中的节点的社区归属具有亦此亦彼性。重叠社区发现方法虽然允许一个节点可以同时属于多个社区,但目前尚缺乏刻画重叠节点归属不同社区的程度指标。该指标的缺乏严重阻碍了对社区的挖掘和分析。为了验证该测度的有效性和合理性,提出了基于贪婪策略的重叠社区发现方法、基于归属不确定性的社区节点重要度排序算法和基于Pareto原理的重叠社区发现方法。基于贪婪策略的重叠社区发现方法克服了处于社区边缘的节点与其他社区的联系被人为割裂的问题,基于归属不确定性的社区节点重要度排序算法针对社区发现结果难以理解的问题提出解决方案,基于Pareto原理的重叠社区发现方法弥补了基于贪婪策略的重叠社区发现方法中存在的重叠节点数量相对较多的不足。第三,提出了基于重叠节点归属不确定性的变规模重叠社区发现方法。在该方法中,根据力学中的力的分解原理对前面提出的重叠节点归属不确定性测度进行了改进。该方法不但可以达到与目前拓扑势方法相当的发现效果,还能提供较之相对宏观或微观的社区,实现了对社区规模的控制和定制。第四,提出了基于拓扑势社区发现的无损网络压缩方法。为满足不同的需求,此项研究提出了两个网络无损网络压缩方法。一个方法以节点与社区代表点的相对距离为依据进行节点重要性的判断,区分不同距离节点的重要性,进而实现按层次的网络无损压缩;另一个方法以节点在社区构成中所起的作用为依据以判断节点的重要性,并对节点的重要性进行了量化,实现了按压缩比率的网络无损压缩。对比实验表明,两种方法不但可以获得理想的压缩率,保留社区间的关联关系,而且可以根据需要在压缩过程中保留社区中的重要节点或社区基本结构。