论文部分内容阅读
从社会系统到信息系统，从技术系统到生物系统，都可以用复杂网络来表示。目前所研究的复杂网络(1)在规模上比过去的网络更大(例如在线社会网络)，或者(2)有时候以去中心化的形式存在(例如非结构化P2P网络)，或者(3)同时满足以上两种情况(例如Web)。这些因素使得我们以整体的方式来分析这些网络变得不可行。处理这个问题的其中一种方法就是采样，即，从原始网络中获得节点和边的子集，然后在获得的子图上进行分析和挖掘。
传统的采样工作主要侧重于推断节点的属性。与这些传统的工作不同，本文的研究工作主要侧重于利用采样来获得原始网络的样本子图，该子图是原始网络的一个密集表示。对于采样，本论文的具体工作包括：
1.本论文从一种全新的角度--社团结构--来研究复杂网络中的采样。基于社团结构的扩张率评价指标，本论文提出了一种全新的采样算法--快速扩张率采样。通过该算法生成的样本网络能够很好地代表原始网络的结构特征。在多个真实网络上的实验结果表明，该算法优于目前性能最好的采样算法，同时时间复杂度更低。
同时，与随机游走类似，本论文将采样和搜索都视为复杂网络上的游走问题。对于搜索，本论文的具体工作包括：
2.与快速扩张率的算法思想相同，基于社团结构的电导率评价指标，本论文提出了一种新的搜索策略--电导率搜索。在多种随机图模型和真实网络上的实验结果表明，该算法比目前己知的搜索算法在平均搜索步数和时间复杂度上具有更好的性能。
3.本论文借用在搜索的理论模型研究中被广泛使用的贪婪搜索公式，从概率分析的角度对搜索任务进行分析，提出了一种新的搜索算法--概率贪婪算法。在随机图模型和真实网络上的同样实验证明了该算法的有效性。
4.在某些应用场景中，例如隐私保护P2P网络中，成功找到目标节点并不是搜索的最终目的，而是需要建立一条从起始节点到目标节点的路径。基于这样一种应用场景，本文提出一种搜索路径的简单短路算法，该算法能够将搜索路径的长度减小一个数量级。
5.本论文提出了样本覆盖率的概念，并从理论上证明了找到具有最大覆盖率的样本是一个NP-hard问题，并利用样本覆盖率来推断不同网络的可搜索性。
以上这些研究工作有助于理解各种通过局部拓扑结构信息完成路由的分布式系统。