基于马尔科夫过程亚稳性的复杂网络簇结构分析和识别方法.pdf

(19)中华人民共和国国家知识产权局

(12)发明专利说明书

(10)申请公布号CN101901251A

(43)申请公布日2010.12.01

(21)申请号CN201010210628.6

(22)申请日2010.06.28

(71)申请人吉林大学

地址130012吉林省长春市前进大街2699号

(72)发明人杨博刘大有

(74)专利代理机构

代理人

(51)Int.CI

G06F17/30

权利要求说明书说明书幅图

(54)发明名称

基于马尔科夫过程亚稳性的复杂网

络簇结构分析和识别方法

(57)摘要

一种基于马尔科夫(Markov)过程亚

稳性的复杂网络簇结构分析和识别方法，

包括下列主要步骤：构造给定复杂网络上

的马尔科夫过程；计算该马尔科夫过程的

转移概率矩阵；计算矩阵的特征值；通过

分析特征值计算出网络簇个数；计算马尔

科夫过程的第一个亚稳态；根据第一个亚

稳态识别出网络的全部网络簇及其层次结

构。本发明为复杂网络簇分析和识别提供

一种全新和高效的方法，与现有同类方法

相比，具有无偏(不依赖主观定义的优化目

标或启发式规则)、计算速度快(具有近似

线性的计算时间复杂性)、识别精度高(能

够准确识别出现实世界中复杂网络的网络

簇及其层次结构)和无监督(不需要先验知

识)的特性。

法律状态

法律状态公告日法律状态信息法律状态

权利要求说明书

1.一种复杂网络簇结构分析和识别方法，其特征在于，包括如下步骤：

构造给定复杂网络N上的一个Markov过程X；

计算X的一步转移概率矩阵P，并计算矩阵I-P的特征值；

通过特征值计算出N的网络簇个数K；

计算X的第一个亚稳态Ssub1/sub；

根据Ssub1/sub识别出N的K个网络簇及其层次结构。

2.根据权利要求1所述的复杂网络簇结构识别方法，其特征在于，该方法采用如下

基本原理识别复杂网络中的网络簇结构：

普遍存在的复杂网络分簇现象是复杂网络内在亚稳性的外在表现形式。具有簇结构

的复杂网络上的Markov过程在向其全稳态演化的极限过程中会经历某些亚稳态。

第一个亚稳态对应的Markov过程转移概率矩阵包含了网络簇的大部分信息，从而

通过计算、分析Markov过程的第一个亚稳态可以识别出网络簇形态、个数和层次

结构等网络簇结构信息。

3.根据权利要求1所述的复杂网络簇结构识别方法，其特征在于，复杂网络上的一

个Markov过程是按照如下方法构造的：

假设网络中存在一个Agent，该Agent能够沿着网络连接从一个网络节点随机的移

动到其它网络节点。X＝{Xsubt/sub，t≥0}表示Agent在不同时刻位置构成的

随机序列，P{Xsubt/sub＝i，1≤i≤n}表示Agent经过t时间到达网络节点i的概

率。由于Agent在t时刻的位置唯一地由其在t-1时刻的位置决定，而和t-1时刻之

前的位置都无关，即满足：

P(Xsubt/sub＝isubt/sub|Xsub0/sub＝isub0/sub，Xsub1/sub

＝isub1/sub，…，Xsubt-1/sub＝isubt-1/sub}＝P(Xsubt/sub＝

isubt/sub|Xsubt-1/sub＝isubt-1/sub}

因此随机序列X满足马尔科夫性，是一个离散、时齐的Markov过程。

4.根据权利要求1所述的复杂网络簇结构识别方法，其特征在于，复杂网络上的

Markov过程的一步转移概率矩阵P是按照如下方法计算的：

P＝Dsup-1/supA

其中矩阵A＝(asubij/sub)subn×n/sub表示网络的邻接矩阵，D＝

diag(dsub1/sub，…dsubn/sub)表示网络的度矩阵，其中dsubi/sub＝

∑subj/suba