24小时热门版块排行榜

返回列表

zhaojia0724

银虫 (小有名气)

应助: 0 (幼儿园)
金币: 1127.6
红花: 1
帖子: 232
在线: 68.9小时
虫号: 2141675
注册: 2012-11-22
性别: MM
专业: 信息理论与信息系统

[求助] 林达华博文中说c2越小越利于信息的迅速扩散这句话来源或理论支撑？

他在《图,谱,马尔可夫过程,聚类结构》一文中说概率转移矩阵中，c2（第二大特征值）越小越利于信息的迅速扩散，请问这个是怎么来的？我表示我的思维无法从收敛转到扩散。。。

谢谢

[ Last edited by zhaojia0724 on 2013-10-16 at 17:18 ]

回复此楼

» 猜你喜欢

祈求上天赐予我平静的心，接受不能改变的事；赐予我勇气，改变可以改变的事；并赐予我分辨二者的智慧。

1楼 2013-10-16 17:17:00

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军

应助: 817 (博后)
金币: 12914.1
红花: 64
帖子: 2238
在线: 287.3小时
虫号: 696514
注册: 2009-02-05
专业: 计算机软件

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感谢参与，应助指数 +1
zhaojia0724: 金币+10, ★★★很有帮助, 谢谢 2013-10-17 08:24:03

根据上面的定义，我们看到邻接矩阵A其实就是这个马尔可夫过程的转移概率矩阵。我们把各个节点的值放在一起可以得到一个向量v，那么我们就可以获得对这个过程的代数表示， v(t+1) = A v(t)。稳定的时候，v = A v。我们可以看到稳定状态就是A的一个特征向量，特征值就是1。这里谱的概念进来了。我们把A的特征向量都列出来v1, v2, ...，它们有 A vi = ci vi。vi其实就是一种很特殊，但是很简单的状态，对它每进行一轮更新，所有节点的值就变成原来的ci倍。如果0 < ci < 1，那么，相当于所有节点的值呈现指数衰减，直到大家都趋近于0。

一般情况下，我们开始于一个任意一个状态u，它的更新过程就没那么简单了。我们用谱的方法来分析，把u分解成 u = v1 + c2 v2 + c3 v3 + ... （在数学上可以严格证明，对于上述的转移概率矩阵，最大的特征值就是1，这里对应于平衡状态v1，其它的特征状态v2, v3, ..., 对应于特征值1 > c2 > c3 > ... > -1)。那么，我们可以看到，当更新进行了t 步之后，状态变成 u(t) = v1 + c2^t v2 + c3^t v3 + ...，我们看到，除了代表平衡状态的分量保持不变外，其它分量随着t 增长而指数衰减，最后，其它整个趋近于平衡状态。

从上面的分析看到，这个过程的收敛速度，其实是和衰减得最慢的那个非平衡分量是密切相关的，它的衰减速度取决于第二大特征值c2，c2的大小越接近于1，收敛越慢，越接近于0，收敛越快。这里，我们看到了谱的意义。第一，它帮助把一个图上运行的马尔可夫过程分解为多个简单的字过程的叠加，这里面包含一个平衡过程和多个指数衰减的非平衡过程。第二，它指出平衡状态是对应于最大特征值1的分量，而收敛速度主要取决于第二大特征值。

我们这里知道了第二大特征值c2对于描述这个过程是个至关重要的量，究竟是越大越好，还是越小越好呢？这要看具体解决的问题。如果你要设计一个采样过程或者更新过程，那么就要追求一个小的c2，它一方面提高过程的效率，另外一方面，使得图的结构改变的时候，能及时收敛，从而保证过程的稳定。而对于网络而言，小的c2有利于信息的迅速扩散和传播。
-----------------------------------------------------

上面是原文节选,highlight了几句关于稳定状态的描述,可以看出作者描述的过程中,网络信息的迅速扩散和传播过程的效率,直接与第二大特征值c2相关.c2越小,收敛越快,效率越高,因此"小的c2有利于信息的迅速扩散和传播".

赞一下

回复此楼

matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com

2楼2013-10-16 17:39:21