【作者】 罗鹏；

【导师】 吴冲；

【作者基本信息】 哈尔滨工业大学 ， 管理科学与工程， 2014， 硕士

【摘要】 抽样网络稳定性是指通过网络抽样方法抽样所得到网络的各种结构特征量与原网络的结构特征量一致性程度。实际生活中存在的网络一般规模巨大，所以如果要研究整体网络，这样数据获得的成本过高或者研究的复杂程度太大，必须要用到网络抽样方法，获得一部分网络数据，但是对于抽样网络是否能具有整体网络的结构特征，是否能保留原网络的真实信息，这样的研究意义非常重大。本文主要对于小概率抽样网络的各种网络结构特征值进行稳定性分析，首先，我们尝试构建两种新的抽样方法，包括改进的分层抽样和改进的滚雪球抽样。基于著名的二八法则，即帕累托法则，认为在网络中一小部分重要的节点拥有网络大部分的网络结构特征，另外Barabasi和Crandall在《Linked: The new science ofnetworks》书中也提到相似的论述。基于这一思路，我们提出的两种抽样方法就是针对小概率网络抽样中高效的寻找到重要节点并抽样该节点。另外对于网络抽样的对象不仅仅是网络节点而且还抽样与该节点相连接的边。然后，本文在三种典型的网络模型中进行仿真实验，包括无标度网络、随机网络和小世界网络，把我们提出的改进分层抽样和改进的滚雪球抽样方法，与现存的抽样方法包括：随机点抽样、随机边抽样、随机分层抽样、滚雪球抽样、随机游走抽样和前沿抽样六种抽样方法，进行比较分析，对于网络的三种网络结构量，网络节点的聚类系数、网络节点的Bonacich中心性和网络平均路径长度，分别进行仿真的结果分析。另外，我们对于各种网络抽样方法进行实证研究，对于实际中的网络数据，蛋白质网络和单词网络，进行比较分析。最后得出结论，新提出的两种抽样方法在五个网络中都能很高效的获取三种网络结构信息，通过这两种新的抽样方法得到的抽样网络的稳定性最高，同时也分析了其他抽样方法在各种不同的网络中的表现。更多还原

【Abstract】 The stability of sampled network is a degree of consistency between the structurecharacteristics of sampled network and that of the original network. As the network sizein the real world is enormous, the cost of acquiring the data is too large, and thecomplexity of research is too big. The sampling method is used to obtain part of thenetwork and decrease the cost of research. But whether the structure of samplednetwork is in accordance with that of the original network or the sampled network canown the real structure information of the original network is a very significant question.This paper studies the stability of the sampled network with low probability. Firstly,we propose two new sampling methods, i.e., improved stratified random sampling(ISRS) and improved snowball sampling (ISBS). The two new sampling methods arebased on the Pareto rule (80/20rule),and we think that a small part of vertices withhigh node degree can possess the most structure information of a network which is alsopresented in the book titled “Linked: The new science of networks”. Besides, we alsosample the network node as well as the edge linked it. The two proposed samplingmethods are efficient in sampling the nodes with high degree. Secondly, in order todemonstrate the two methods’ availability and accuracy, we compare them with theexisting sampling methods in three commonly used simulation networks that arescale-free network, random network, small-world network, and two real networks. Weanalyse the clustering coefficient, Bonacich centrality and average path distance of thenetwork. Besides, the tests in two real networks are provided further.In conclusion, we can get that the two proposed sampling methods perform muchbetter than the compared existing sampling methods in terms of sampling cost andobtaining the true network structural characteristics. The sampled network of the twoproposed sampling methods are more stable, and we also research the differentperformance of the other sampling methods in different networks.更多还原