为什么我们要管复杂网络叫复杂网络呢？换言之，“复杂”是什么意思？

这么说也就意味着有些网络不是复杂的，或者说，有些网络比另一些更复杂。这个怎么衡量呢？

看了张学文（《组成论》中）对“广义集合”和“复杂程度”的描述后，我马上想到，衡量网络复杂程度的公式，其实就是建立在节点度分布的公式基础上！

考虑一个无向网，如果一个网络的节点度分布是个常数，那这个网络可真够简单的，但如果一个网络中每个节点的度数都不一样，那这个网络就非常复杂了。

如果注意一下张学文提出的复杂程度公式，就知道其实就是信息熵的公式，越复杂的网络，熵也就越大。

换一个角度，使用一个叫“最小描述长度”的概念来说这个事（我们在这里不追究这个概念在数据处理中的具体意义，而是在比喻意义上使用之），我用一句话就能说清楚：“A网络中10个节点度都是4”，你就可以画出来这个拓扑结构而不丧失信息；但如果是“B网络中10个节点度都不一样，第一个是10，第二个是9···”就最小描述长度而言，后者就要多花一些bite的信息来描述这个拓扑结构，因此更复杂。

当我们知道网络的复杂程度原来是可以计算，可以比较后，我们不仅要问：复杂网络有没有一个一般趋势呢？网络是总会变得更复杂，还是变得更简单？

这就是复杂网络的演化了。

复杂网络之所以解释力强，就是因为它将复杂系统的特征概括为一个拓扑结构，复杂系统的演化可以被几何地表示为这个拓扑结构的演化，又可以被确定地计算出来，因此是一个很好的模型。

另外还有一点非常值得注意，为何复杂网络中节点的度分布往往都是power law，这个问题的关键在于，power law公式与信息熵的公式是一样（请暂时容忍这种不精确的说法）的。

有人会说，你自己前面说了节点的度分布代表着信息嘛，所以当然和信息熵公式一样。但是我觉得没这么简单，因为我们之前测量度分布的时候，是没有想过是要得到信息总量的，我们在拟合数据的时候，也是因为它自己就呈现power law的统计分布，所以才管它叫幂律，如果度分布不是一个幂律分布而是正态分布，甚至是一个常数，它也仍然代表着信息量呀！所以它完全不必非得长成幂律形状。

那为什么它在复杂网络中就呈现出和信息熵一个的log底公式呢？

我觉得这就是“观察者”的结果了，当对象太复杂，需要处理的信息超出了心智的“上限”，我们就只能看到自己想（或说，不得不）看到的pattern了，也就是这个时候，看到的不是信息，而是我们用于处理信息的“滤波”结构···

（二）2009-05-19

继续之前的思路，计算一个复杂网络的熵，最小值在所有点的度为一个常数时达到（log1=0,因此熵为0），最大值为所有点的度数都不一样时达到（sigma(Pi)log(Pi)=logN）。越靠近后者的分布熵越大，越“复杂”。

这个就定性地回答了jake说的为什么Erdos-renyi随机网没有scale-free网络复杂的问题——后者更靠近最大熵分布（直线），但还需要进一步的数学证明。

（三）2009-06-10


在旭东的帮助下，我们终于把各类分布画到一个图上了（possion本来是离散的，为便于观察，在这里显示为连续的太。此外，抽象不好，我们可以把这个图就看做是网络度分布的图。不过这个图不精确，因为这些分布的参数是我们自己调的）。中间那个x=0.5就是熵最小的情况，平行于X轴的线是熵最大的情况。所有的分布都应该是这一横一竖“夹”出来的。

为何不在这个图中画出一条Y=1的线呢？我认为，在这个图里，越“平”的线，熵越大，而这些分布与X轴夹的面积大小，可以用来衡量“平”的程度。所以X轴可以用来代替Y=1。

旭东提出，其实各种分布的熵究竟是多少，一算就知道。但我们当时没有精确计算。同时我回忆起《组成论》随想录里，冯向军为张学文老师做的一个分析证明，方差和熵是正比的，我找到了这个模拟图：



（附冯对MSD的定义：
假设广义集合仅有2个标志值: v1 = 1; v2 = 2. 令v1,v2 的概率分别为 p1, p2, 则有标志值均值为
M = p1v1 + p2v2      (1)
我们定义标志值相对其均值的均方距MSD为标志值分散度.则有
MSD = p1(v1 - M)2 + p2 (v2 - M)2      (2)
实际上， 倘若视标志值为随机变量，则MSD即为此标志值随机变量的方差。）


那这么说的话有如下命题待证

1.正态分布的熵和泊松分布的熵比指数和幂律小，因为前者靠近“竖线”，后者靠近“横线”

2.同理，正态分布的熵和泊松分布的方差比指数和幂律小。问题在于在我们画的图里，方差可是自己调的。但我仍然坚持这个判断。并且我认为这个和Scale free的问题相关。

正态分布有一个均值，按照barabasi说法，以网络为例，有charactor node可以代表大多数点，因此自然方差较小，而幂律这样scale free的，几乎每个node都在不同的量级上，没有什么可以代表大部分点的node，方差自然大。
(张江指出，幂律分布是唯一方差无限大的分布，因为没有均值（？）)