更改

==简介==

==简介==

使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。

使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。

==构建一个点击流网络==

==构建一个点击流网络==

假设我们手头有一批用户在一段期间内访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（user visit）排名前V的资源，得到节点集合|V|，然后对于一个用户i在一段时间内（例如一天）内访问的资源，选择属于|V|的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。

假设我们手头有一批用户在一段期间内访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（user visit）排名前V的资源，得到节点集合|V|，然后对于一个用户i在一段时间内（例如一天）内访问的资源，选择属于|V|的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。

对于一天内的n个用户做这个操作，最后将得到的总数为 的连边里相同的边合并，得到|M|个不同的边，每条边上都带有权重信息。这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。

对于一天内的n个用户做这个操作，最后将得到的总数为 的连边里相同的边合并，得到|M|个不同的边，每条边上都带有权重信息。这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。

==网络社区划分的两种主要思路：拓扑分析和流分析==

==网络社区划分的两种主要思路：拓扑分析和流分析==

| Role-based community || 划分出在流中地位类似的节点 || |V|^3 || 有向有权单分量 || 结果不稳定

| Role-based community || 划分出在流中地位类似的节点 || |V|^3 || 有向有权单分量 || 结果不稳定

|-

|-

|}

|}

 

上表中的分量 component指在网络中的独立“团块”。有向网络里，分量有强弱之分，强分量（strong component ）中任意一个节点都可到达另外一个节点，弱分量 weak component中如果忽略连边方向，则构成强分量。无向网里分量没有强弱之分。在网络中识别强分量的算法有Kosaraju算法，Tarjan算法及其变形Gabow算法等。在这里不展开叙述。

 

上表中的分量（component）指在网络中的独立“团块”。有向网络里，分量有强弱之分，强分量（strong component ）中任意一个节点都可到达另外一个节点，弱分量（weak component）中如果忽略连边方向，则构成强分量。无向网里分量没有强弱之分。在网络中识别强分量的算法有Kosaraju算法，Tarjan算法及其变形Gabow算法等。在这里不展开叙述。

接下来，我们逐一讨论拓扑分析和流分析中的各种算法的具体思路。

接下来，我们逐一讨论拓扑分析和流分析中的各种算法的具体思路。

==拓扑分析==

==拓扑分析==

===计算网络的模块化程度 Q-Modularity ===

===计算网络的模块化程度 Q-Modularity ===

Q-Modularity是一个定义在[-0.5,1)区间内的指标，其算法是对于某一种社区结构，考虑每个社区内连边数与期待值之差。实际连边越是高于随机期望，说明节点越有集中在某些社区内的趋势，即网络的模块化结构越明显。Newman在2004年提出这个概念最初是为了对他自己设计的社区划算法进行评估，但因为这个指标科学合理，而且弥补了这个方面的空白，迅速成为一般性的社区划分算法的通用标准。

Q-Modularity是一个定义在[-0.5,1)区间内的指标，其算法是对于某一种社区结构，考虑每个社区内连边数与期待值之差。实际连边越是高于随机期望，说明节点越有集中在某些社区内的趋势，即网络的模块化结构越明显。Newman在2004年提出这个概念最初是为了对他自己设计的社区划算法进行评估，但因为这个指标科学合理，而且弥补了这个方面的空白，迅速成为一般性的社区划分算法的通用标准。

Q的具体计算公式如下：

Q的具体计算公式如下：

:<math>Q=\sum_{ij}{\left [  {\frac{A_{ij}}{2m}-\frac{k_{i}*k_{j}}{(2m)(2m)}}\right ]}\delta (c_{i},c_{j})=\sum_{i=1}^{c}(e_{ii}-a_{i}^{2})</math>

:<math>Q=\sum_{ij}{\left [  {\frac{A_{ij}}{2m}-\frac{k_{i}*k_{j}}{(2m)(2m)}}\right ]}\delta (c_{i},c_{j})=\sum_{i=1}^{c}(e_{ii}-a_{i}^{2})</math>

上式已经清楚定义了<math>Q</math>，但在实际计算里，上式要求对社区及其内部节点进行遍历，这个计算复杂度是很大的。Newman(2006)对上式进行了化简，得到矩阵表达如下：

上式已经清楚定义了<math>Q</math>，但在实际计算里，上式要求对社区及其内部节点进行遍历，这个计算复杂度是很大的。Newman(2006)对上式进行了化简，得到矩阵表达如下：

我们定义<math>S_{ir}</math>为<math>n*r</math>的矩阵，<math>n</math>是节点数，<math>r</math>是社区数。如果节点<math>i</math>属于社区<math>r</math>，则为1，否则为0。则有

我们定义<math>S_{ir}</math>为<math>n*r</math>的矩阵，<math>n</math>是节点数，<math>r</math>是社区数。如果节点<math>i</math>属于社区<math>r</math>，则为1，否则为0。则有

本文中我们总结了构建点击流网络之后，使用社区划分算法来对点进行聚类的不同思路。主要可以分为拓扑分析和流分析两种，从数学角度看，前者以频谱分析（Spectral analysis）为主要手段，后者以马可夫链（Markov chain）为主要建模工具。其中流编码算法较为独特，以信息论为主要工具。但值得注意的是，由于编码算法仍然是在处理流，所以本质上只是对马可夫链的一种处理。例如在图4中，编码算法没有能区分开节点，而是将所有的节点归为一个区，每个节点被访问的流概率恰好等于其Page rank值（与节点的大小和颜色深度成正比）。而我们知道Page rank也仍然是基于马可夫链的。这个时候平均每走一步要消耗2.71比特信息。

本文中我们总结了构建点击流网络之后，使用社区划分算法来对点进行聚类的不同思路。主要可以分为拓扑分析和流分析两种，从数学角度看，前者以频谱分析（Spectral analysis）为主要手段，后者以马可夫链（Markov chain）为主要建模工具。其中流编码算法较为独特，以信息论为主要工具。但值得注意的是，由于编码算法仍然是在处理流，所以本质上只是对马可夫链的一种处理。例如在图4中，编码算法没有能区分开节点，而是将所有的节点归为一个区，每个节点被访问的流概率恰好等于其Page rank值（与节点的大小和颜色深度成正比）。而我们知道Page rank也仍然是基于马可夫链的。这个时候平均每走一步要消耗2.71比特信息。

[[category:旧词条迁移]]

 

 

 

 

 

 

 

本中文词条由[[用户:薄荷|薄荷]]编辑，如有问题，欢迎在讨论页面留言。