统计网络模型若干关键问题研究

《统计网络模型若干关键问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、提要现实世界的诸多关系均以复杂网络的形式存在，对复杂网络的研究具有重要的理论意义和应用价值。统计网络模型作为复杂网络和机器学习等领域的重要研究内容之一，有助于人们了解网络的结构特性、生成机制及发展演化，有助于人们探索隐含在网络背后的本质规律。近年来，随机块模型与随机游走模型吸引了学者的广泛关注，成为当前复杂网络领域的研究热点，众多研究成果表明两类模型具有诸多优点，在结构模式发现、链接预测、节点排序等方面表现出了优秀的性能。然而由于复杂网络/复杂系统的复杂性，两类统计模型面临着一些挑战与难题。本文重点关注了随机块模型与随机游走模型，深入研究了它们在网络建模、统计推理、模型

2、应用等方面的若干关键问题：1）针对现有随机块模型无法处理符号网络的问题，提出了一种新的符号随机块模型及其学习算法，有效解决了符号网络的统计建模问题，并首次利用统计网络模型与变分推理方法解决了符号网络的社区发现问题；2）针对现有随机块模型学习算法时间复杂度过高的问题，提出了一种新的细粒度随机块模型及其快速学习算法，首次实现了随机块模型参数估计与模型选择的并行学习机制，有效降低了随机块模型学习的时间复杂度；3）基于社区结构特性，在随机游走模型框架内提出了一种新的节点排序算法，实现了利用社区描述的全局结构和近邻节点序列描述的局部结构进行节点排序，此外，为了降低在线计算时间、有

3、效处理大规模网络，为该算法提供了一种线下/在线计算方案。在人工网络与真实网络上的实验结果表明本文提出的这些模型与算法均具有较好的性能，达到了预期的效果和目的。摘要摘要统计网络模型若干关键问题研究现实世界的诸多关系均以复杂网络的形式存在，对复杂网络的研究具有重要的理论意义和应用价值。统计网络模型作为复杂网络和机器学习等领域的重要研究内容之一，有助于人们了解网络的结构特性、生成机制及发展演化，有助于人们探索隐含在网络背后的本质规律。近年来，随机块模型与随机游走模型吸引了学者的广泛关注，成为当前复杂网络领域的研究热点，众多研究成果表明两类模型具有诸多优点，在结构模式发现、链接

4、预测、节点排序等方面表现出了优秀的性能。然而由于复杂网络/复杂系统的复杂性，两类统计模型面临着一些挑战与难题。本文重点关注了随机块模型与随机游走模型，深入研究了它们在网络建模、统计推理、模型应用等方面的若干关键问题，针对随机块模型及学习算法存在的不足，本文提出了新的思路与方案；针对随机游走模型，在结构发现与节点排序的融合研究中提出了新的解决思路。本文主要研究成果如下：1）针对现有随机块模型无法处理符号网络的问题，提出了一种新的符号随机块模型及其学习算法，有效解决了符号网络的统计建模问题，并首次利用统计网络模型与变分推理方法解决了符号网络的社区发现问题。现有的随机块模型可

5、以有效处理链接的方向及权重，然而无法处理链接的符号。近年来，大量出现的符号网络对随机块模型无法处理链接符号这一问题提出了挑战。为此，本文在标准随机块模型的基础之上，提出一种新的可建模符号网络的符号随机块模型，该模型从网络噪声角度出发对网络的正、负链接进行建模，既解决了原有随机块模型无法处理符号网络的问题，也有效提高了符号网络社区发现的精度，同时还可进行符号预测。另外该模型也是一个符号网络生成模型，可以生成具有不同社区特性的人工符号网络。随后，针对符号随机块模型提出一种具有模型选择能力的学习算法，该算法利用变分贝叶斯EM估计变量与参数的近似分布，同时在变分贝叶斯框架下推导

6、出一个新的模型选择标准，该标准利用证据的低边界对模型进行评价。与现有算法相比，提出的算法不仅可以更有效地对零先验结构知识的符号网络进行社区发现，同时可以用于符号预测及网络平衡性分析。2）针对现有随机块模型学习算法时间复杂度过高的问题，提出一种新的细粒度随机块模型及其快速学习算法，该算法首次实现了随机块模型参数估计与模型选择的并行学习机制。现有随机块模型学习算法通常都采用参数估计与模型选择的串行学习机制，该机制下大量已获取的信息需要重新计算致使学习算法的时间复杂度过高，也使得现有学习算法面对零先验结构知识的真实网络时仅能处理几百节点的小规模网络，大大限制I吉林大学博士学位

7、论文了模型的应用。为此，本文首先提出了一种新的细粒度随机块模型，该模型利用块-节点连接概率矩阵代替标准随机块模型的块连接概率矩阵，使得模型在保留随机块模型原有特性的基础上可以描述更细致的结构并具有更高的泛化能力。最重要的是，细粒度随机块模型可以提供一种更有效的可降低时间复杂度的学习方式。随后，基于该模型提出了一种具有模型选择能力的快速学习算法，该算法整合了最小信息长度标准与期望最大化算法，实现了基于块的并行学习机制，在该机制下并行执行模型选择与参数估计，对不好的模型不再反复学习，大量减少了原有学习算法的重复计算，以此方式显著降低了学习的时