复杂网络性质及传播动力学行为研究

【作者】 孙仁诚；

【导师】 邵峰晶；

【作者基本信息】 青岛大学 ， 系统理论， 2010， 博士

【摘要】 近十年来,复杂网络的研究取得了重要成果,主要体现在构建网络拓扑模型,分析网络性质,复杂网络上的传播动力学、复杂网络的同步与控制以及一些实证研究等方面。本文在对复杂网络的概念和研究动态分析概括的基础上,讨论了数据挖掘与复杂网络研究的相关性,研究了可用于复杂网络分析的相关的数据挖掘算法：针对FP-TREE算法的序列发现效率问题,通过改进FP-TREE的结构,提出了一种具有较高挖掘效率的序列模式发现算法：在保证分类精度降低较少的前提下,通过在TSVM引入预测距离闽值,提出了一种提高分类效率的半监督学习方法；针对复杂网络社团发现算法中结点相似度度量问题,应用半监督学习及信息传播的思想,给出了结点相似性度量方法,定义了网络结点信息传播的两种方式：扩散传播与吸收传播方式,并证明了在这两种传播方式下结点的信息传播与结点信息向量表达之间的一致性及信息传播的收敛性,为复杂网络社团发现与数据挖掘聚类问题,提供了转化途径。采用数据挖掘聚类算法对结点相似性度量方法进行验证,结果表明了该方法对社团划分的有效性；针对基于结点信息向量随着网络规模不断增加难以使用聚类算法完成对大规模网络划分社社团的问题,提出了一种基于单源信息传播的社团发现算法,并采用典型的测试网络验证了该算法的有效性。对我国12座大中城市的公交线路网络的复杂性进行分析,采用基于单源信息传播社团发现算法完成了公交线路网络社团划分。研究了多信息传播时,结点状态的复杂性,给出传播机制、作用机制和感染机制的定义,提出具有抑制作用的多信息传播模型SIn,并进行了仿真分析,结果与解析解较好吻合。考虑网络拓扑结构对传播的影响,针对两种信息相互作用产生变异的情况,研究了异质网上的多信息传播过程,提出一种接触变异的传播模型—CM传播模型。分析了系统的相变情况,在不同传播率和变异率下信息传播动力学过程,社团结构对信息传播影响。网络拓扑结构影响信息传播,信息传播也会影响网络的拓扑演化。通过分析信息传播过程与网络拓扑结构的随时间同步演化并相互作用,建立了一种基于网络结点状态的优先连接规则的动态增长网络模型,分析了该模型的拓扑性质。并研究了基于此模型的传播动力学行为。更多还原

【Abstract】 In recent ten years, research of complex network has achieved a lot in many aspects, such as modeling topology of networks, analyzing character of networks, dynamics on networks, synchronization and control of networks and empirical study of networks.With consideration of topology effecting information propagation, the relationship of data mining and complex network is discussed, and the relevant data mining algorithm is studied: through improving the structure of the FP-TREE, an algorithm of mining sequential patterns is proposed, which is the higher efficiency. Ensuring accuracy of classification, according to introducing TSVM distance threshold to predict, a semi-supervised learning method to improve the efficiency of classification is proposed. A new similarity method of nodes is proposed for community detection of complex networks. By transferring from topology similarity to vector similarity of nodes, community detection turns out to spatial data clustering. Two types of information propagation of nodes, diffusion and absorbing spreading, are defined. Consistency between information spreading and information vector of node and convergence of information spreading under these two types propagation are testified.By adopting clustering algorithms in data mining for testifying method of information vector used in community detection, efficiency of this method is proved. For inefficiency of community detection in large networks by using information vector method mentioned above, a new algorithm based on single information spreading is proposed. Typical empirical networks are used to testify its validity.Analyzing complexity of transportation networks in twelve cities of our country, community detection in those networks are archived by single information spreading mentioned above.Complexity of node state is studied and mechanism of propagation and interaction and infection are defined when multi-information spreading. Multi-information propagation model Sln with inhibiting function is proposed. The results of this model are investigated analytically and by simulations.Based on analyzing and summarizing concept and development of complex network, a variation spreading model caused by contact among of three messages and named CM model, is proposed, it has been analyzed that system transition, the dynamic process of information transmission with the different spreading rate and variation rate, and the effect with community structure.Spreading of information affects the formation of topology of networks. By analyzing the coevolving and interaction between information propagation and formation of network topology, a dynamic growth network model is proposed. In the model, the links of a new node depends on the state and degree of nodes. On this model, dynamics of and on this network are studied.更多还原