7,129
个编辑
更改
→流编码算法 the Map Equation
Rosvall和Axelsson 2009年提出了一种很有意思的方法来研究网络中的流动。其核心思想是，好的社区划分要令网络上流的平均描述长度最短。他们认为，分析有向加权网络的一个好的视角是观察某类实体（货币、能量、信息）在网络上的流动。即使没有实体流动的数据，我们也可以根据网络的基本结构来推测随机游走的粒子的轨迹，然后对得到的“平均流”进行信息编码。对“平均流”的描述长度最短的编码机制，就对应着对社区的一种最有效划分。
Rosvall和Axelsson 2009年提出了一种很有意思的方法来研究网络中的流动。其核心思想是，好的社区划分要令网络上流的平均描述长度最短。他们认为，分析有向加权网络的一个好的视角是观察某类实体（货币、能量、信息）在网络上的流动。即使没有实体流动的数据，我们也可以根据网络的基本结构来推测随机游走的粒子的轨迹，然后对得到的“平均流”进行信息编码。对“平均流”的描述长度最短的编码机制，就对应着对社区的一种最有效划分。
首先要讨论的是节点层编码。最简单的方式是给每个节点分配一个独特的二进制签名。但这种编码方式并不高效，因为节点被访问的概率并不一样。为了改进，我们可以引入一个Huffman编码表（code book），在这个编码表上，每个节点都对应一个独立的二进制编码，但码长与节点被访问的概率（通过转移矩阵P在无穷步后的收敛结果来计算）相反。这样，“平均流”的信息长度就大大被降低了。
首先要讨论的是节点层编码。最简单的方式是给每个节点分配一个独特的二进制签名。但这种编码方式并不高效，因为节点被访问的概率并不一样。为了改进，我们可以引入一个Huffman编码表（code book），在这个编码表上，每个节点都对应一个独立的二进制编码，但码长与节点被访问的概率（通过转移矩阵P在无穷步后的收敛结果来计算）相反。这样，“平均流”的信息长度就大大被降低了。
其次，我们还可以通过引入两层编码，节点编码和社区编码，来进一步降低信息长度。有了社区编码的好处是，两个或多个社区内部的节点编码是可以重复的，这就进一步降低了信息长度。需要注意的是，两层编码并不意味着像国际电话区号那样，在每个节点前加一个社区前缀码，因为这样的话其实就和单层编码没有什么区别了。这里的两层编码实际上是在利用流的“局域性”。只需要我们标识出社区的入口（即社区编码）和出口（定义在社区间连边上的编码），在此区域内访问的节点，可以直接使用节点层的编码，不用考虑社区编码。例如：11-0000-11-01-101-100-101-01-0001-0-110-011-00-110-00-111-… 在这个流中，加粗的0前面，节点都在一个社区里游走，所以直接使用节点编码，0001是一个社区出口连边（exit）编码，使用了这个编码意味着节点要跳转社区，接下来0这个社区编码被使用，意味着流进入0社区，在这里面再次直接使用节点编码，直到跳出0社区（0社区的exit被使用）。
其次，我们还可以通过引入两层编码，节点编码和社区编码，来进一步降低信息长度。有了社区编码的好处是，两个或多个社区内部的节点编码是可以重复的，这就进一步降低了信息长度。需要注意的是，两层编码并不意味着像国际电话区号那样，在每个节点前加一个社区前缀码，因为这样的话其实就和单层编码没有什么区别了。这里的两层编码实际上是在利用流的“局域性”。只需要我们标识出社区的入口（即社区编码）和出口（定义在社区间连边上的编码），在此区域内访问的节点，可以直接使用节点层的编码，不用考虑社区编码。例如：11-0000-11-01-101-100-101-01-0001-0-110-011-00-110-00-111-… 在这个流中，加粗的0前面，节点都在一个社区里游走，所以直接使用节点编码，0001是一个社区出口连边（exit）编码，使用了这个编码意味着节点要跳转社区，接下来0这个社区编码被使用，意味着流进入0社区，在这里面再次直接使用节点编码，直到跳出0社区（0社区的exit被使用）。
在这个两层编码体系中，包括三类码表（code book）。第一个是主码表（master code book），决定每个社区的编码；第二个是传送门码表（exit code book），决定每个社区的出口连边的编码；第三个是节点码表（node code book），决定每个社区内的节点的编码。一旦对网络的社区划分P（partition）给定，就存在一个社区码表，一个传送门码表，和m个节点码表，其中m是社区的个数。最后，社区划分的目标就是要最小化所有码表的总长，或者按论文中的说法，平均随机游走中的一步所耗费的信息成本。
在这个两层编码体系中，包括三类码表（code book）。第一个是主码表（master code book），决定每个社区的编码；第二个是传送门码表（exit code book），决定每个社区的出口连边的编码；第三个是节点码表（node code book），决定每个社区内的节点的编码。一旦对网络的社区划分P（partition）给定，就存在一个社区码表，一个传送门码表，和m个节点码表，其中m是社区的个数。最后，社区划分的目标就是要最小化所有码表的总长，或者按论文中的说法，平均随机游走中的一步所耗费的信息成本。
[[File:community_figure_11.png|600px]]
[[File:community_figure_11.png|600px]]
其中M即对网络的某种社区划分得到m个社区。L是该划分所对应的信息描述长度。qi->代表进出第i个社区的概率（先考虑无向网络），因此q->代表社区间跳转的总概率。H(Q)是社区间跳转行为的香农信息量。Pi->代表第i个社区内节点间跳转的总概率，H(Pi)是第i个社区内节点间跳转行为的香农信息量。在公式的两个部分，信息量都用其被使用的频率进行加权。经过展开化简，可以得到简化形式如下：
[[File:community_figure_12.png|400px]]
[[File:community_figure_12.png|400px]]
最后，使用某种社区划分的搜索策略（主要有细分与合并两种）来寻找该描述长度的最小值即可。值得注意的是，在实际计算中，节点层的信息量（第三项）是不需要考虑的。
最后，使用某种社区划分的搜索策略（主要有细分与合并两种）来寻找该描述长度的最小值即可。值得注意的是，在实际计算中，节点层的信息量（第三项）是不需要考虑的。
<br>
===流层级算法 Role-based Similarity===
===流层级算法 Role-based Similarity===