网络社区划分算法

网络社区划分算法

目录

?1简介

?2构建一个点击流网络

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

?4拓扑分析

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

o 4.2计算网络的连边紧密度Edge betweenness

o 4.3计算网络拉普拉斯矩阵的特征向量Leading eigenvector

o 4.4通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值

o 4.5通过multi level方法搜索网络模块化程度Q-Modularity的最大值

?5流分析

o 5.1随机游走算法Walk Trap

o 5.2标签扩散算法label propagation

o 5.3流编码算法 the Map Equation

o 5.4流层级算法 Role-based Similarity

?6总结

[]简介

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

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

这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。

社区划分的算法比较多，但我个人认为大致可以分为两大类：拓扑分析和流分析。前者一般适用于无向无权网络，思路是社区内部的连边密度要高于社区间。后者适用于有向有权网络，思路是发现在网络的某种流动（物质、能量、信息）中形成的社区结构。这两种分析各有特点，具体应用取决于网络数据本身描述的对象和研究者想要获得的信息。

我们可以将已知的一些算法归入这两类：

算法优化目标计算复杂度适用情况局限

拓扑分析

Q Modularity 最大化Q-modularity V|^2 无向无权多分

量

不适用小网

络

Edge-Betweenness 最小化社区间连边的betweenness V|*|E|^2 有向有权多分

量

慢

Leading Eigenvector 对拉普拉斯矩阵第二小特征根对应的特征向量

聚类

V|^2+ |E|

无向无权多分

量

Fast Greedy 使用社区合并算法来快速搜索最大

Q-modularity

E|*log(|V|)

无向有权多分

量

不适用小网

络

Multi Level 使用社区展开算法来快速搜索最大

Q-modularity V| 无向有权多分量 不适用小网

络

流分析

Walk Trap 最大化社区间的流距离 E|*|V|^2 无向有权单分

量

Label Propagation 每个节点取邻居中最流行的标签，迭代式收敛 V| + |E| 无向有权单分量

结果不稳定 Info map 最小化随机流的编码长度 V|*(|V|+|E|) 有向有权单分量

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

结果不稳定

上表中的分量（component ）指在网络中的独立“团块”。有向网络里，分量有强弱之分，强分量（strong component ）中任意一个节点都可到达另外一个节点，弱分量（weak component ）中如果忽略连边方向，则构成强分量。无向网里分量没有强弱之分。在网络中识别强分量的算法有Kosaraju 算法，Tarjan 算法及其变形Gabow 算法等。在这里不展开叙述。 接下来，我们逐一讨论拓扑分析和流分析中的各种算法的具体思路。

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

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

下：

其中A 是网络G 对应的邻接矩阵，如果从i 到j 存在边，则Aij=1，否则为0。m 是总连接数，2m 是总度数，Aij/2m 是两节点之间连接的实际概率。Ki 和kj 分别是i 和j 的度数。如果我们保持一个网络的度分布但对其连边进行随

机洗牌，任意一对节点在洗牌后存在连接的概率为kikj/(2m)2。上式中中括号表达的就是节点之间的实际连边概率

高于期待值的程度。后面跟着一个二元函数，如果节点ij属于同一个社区，则为1，否则为0，这就保证了我们只考虑社区内部的连边。刚才这个定义是以节点为分析单位。实际上，如果以社区为分析单位看Q指标，可以进一步将其化简为eii和ai之间的差。其中eii是在第i个社区内部的link占网络总link的比例，ai是第i个社区和所有其他社区的社区间link数。

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

如果节点i属于社区r，则为1，否则为0。则有

于是有

其中B是modularity matrix，其元素为

该矩阵的行列和都是0，因为实际网络和随机洗牌后的网络度分布是不变的。特别地，在仅仅有两个社区的情况下（r=2），可以s定义为一个n长的向量，节点属于一个社区为1，属于另一个社区为-1，Q可以写成一个更简单的形式：

通过对社区的划分可能空间进行搜索，可以得到最大化Q值的社区划分。在这个过程会涉及数值优化的部分，例如表一中的fast greedy和multilevel就是用不同方法进行快速搜索的例子。以fast greedy为例Newman（2006），它通过不断合并社区来观察Q的增加趋势，得到了一个在最差的情况下复杂度约为O( |E|*log(|V|) )，在最好的情况下接近线性复杂度的算法。

[]计算网络的连边紧密度Edge betweenness

这个思路出现得比较早(Newman, 2001)。Freeman (1975) 提出过一个叫betweenness的指标，它衡量的是网络里一个节点占据其他n-1节点间捷径的程度。具体而言，首先对每一对节点寻找最短路径，得到一个n * (n-1)/2的最短路径集合S，然后看这个集合中有多少最短路径需要通过某个具体的节点。Newman借鉴了这个标准，但不是用来分析节点而是分析连边。一个连边的edge betweenness就是S集合里的最短路径包含该连边的个数。定义了连边的betweenness后，就可以通过迭代算法来进行社区划分了。具体做法是先计算所有连边的betweenness，然后去除最高值连边，再重新计算，再去除最高值连边，如此反复，直到网络中的所有连边都被移除。在这个过程中网络就逐渐被切成一个个越来越小的component。在这个过程中，我们同样可以用Q-modularity来衡量社区划分的结果。这种算法定义比较清晰，也不涉及矩阵数学等运算，但问题是计算复杂度比较大。

[]计算网络拉普拉斯矩阵的特征向量Leading eigenvector

一个有n个节点的网络G可以被表达为一个n x n的邻接矩阵（adjacency matrix）A。在这个矩阵上，如果节点i 和j之间存在连边，则Aij=1，否则为0。当网络是无向的时候，Aij=Aji。另外我们可以构造n x n的度矩阵（degree matrix）D。D对角线上的元素即节点度数，例如Dii为节点i的度数，所有非对角线的元素都是0。无向网的分析

不存在度数的选择问题，有向网则要根据分析目标考虑使用出度还是入度。将度数矩阵减去邻接矩阵即得到拉普拉斯矩阵，即L = D-A。

L的特征根存在一些有趣性质。首先，最小的特征根总等于0。因为如果将L乘

以一个有n个元素的单位向量，相当于计算每一行的和，刚好是节点的度的自我抵消，结果等于0。其次，特征根中0 的个数即无向网G中分量的个数。这意味着如果除了最小特征根，没有别的特征根为0，则整个网络构成一个整体。

在这些特征根里，第二小的特征根（或者最小的非零特征根）又叫做代数连通性（algebraic connectivity），其对应的特征向量叫做Fidler vector。当，说明网络是一个整体。越大，说明网络彼此间的链接越紧

密。从这个定义来看，非常像前面讨论的Q-Modularity，实际上在Newman2006的文章里，确实讨论了二者在数学上的对应关系。例如对示例网络所对应的进行分析，可以得到拉普拉斯矩阵如下：

这个矩阵的特征根如下：{5.5, 4.5, 4.0, 3.4, 2.2, 1.3, 1.0, 0}。取时， Fidler vector={0.29, 0.00,

0.29, 0.29, 0.29, -0.58, -0.58, 0.00}。因为Fidler vector的值分别对应着图里的节点，于是可以写成{a:0.29, b: 0.00, c:0.29, d:0.29, e:0.29, f:-0.58, g:-0.58, h:0.00}。仅仅从元素的正负号就可以看出，该分析建议我们把f和g节点与其他节点分开，更细致的，对元素值大小的考察则建议把矩阵分成三个社区，{{a, c, d, e}, {b, h}, {e, f}}。回到图中考察，我们发现这个社区分类基本是合理的。

[]通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值

[]通过multi level方法搜索网络模块化程度Q-Modularity的最大值

因为以上两种方法都是基于Q-modularity的，只不过是搜索策略的不同，所以在此不展开讨论。

P. Pons 和 M. Latapy 2005年提出了一个基于随机游走的网络社区划分算法。他们提出可以使用两点到第三点的流距离之差来衡量两点之间的相似性，从而为划分社区服务。其具体过程如下：首先对网络G所对应的邻接矩阵A 按行归一化，得到概率转移矩阵（transition matrix）P。使用矩阵计算表达这个归一化过程，可以写作

其中A是邻接矩阵，D是度矩阵。利用P矩阵的马可夫性质可知，它的t次方的元素Pijt就代表着随机游走的粒子经过t步从节点i到j的概率。其次，定义两点ij间的距离如下：

其中t是流的步长。步长必须恰当选择，因为如果t太小，不足以体现网络的结构特征，如果t太大，则Pijt趋近于与j的度数d(j)成正比，随机游出发点i的拓扑信息被抹去。作者建议的t经验值为3到5之间。k是某一个目标节点。所以这个公式描述的是经过t步，ij到目标节点k的平均流转移概率（因为这个概率与中间节点k 的度数d(k)成正比，所以要除以d(k)来去除这个影响）。ij到网络所有其他点之间的距离差别越小，说明ij很可能位于及其类似的位置上，彼此之间的距离也越接近。值得注意的是，这个思路如果只考虑一个或少数的目标节点，是不合适的。因为rij实际上只是结构对称性。有可能ij在网络的两端，距离很远，但到中间某个节点的距离是相等的。但因为公式要求k要遍历网络中除了ij以外的所有节点，这个时候ij如果到所有其他节点的流距离都差不多，比较可能是ij本身就是邻居，而不仅仅是结构上的对称。如公式所示，rij表达可以写成矩阵表达，其中Pti?是第P的t次方后第i行。

定义了任意两点之间的距离rij后，就可以将其推广，得到社区之间的距离rc1c2了：

容易看出，这个距离与节点之间的距离很相似，只不过这次是计算两个社区分别到目标节点k的流距离，而计算单个社区C到节点k的流距离时，又是对社区C内所有节点到k流距离取平均。

一旦从流结构中提取了节点相似性，社区划分就是一个比较简单的聚类问题。例如可以采取合并式聚类法如下：先将每个节点视为一个社区，然后计算所有存在连边的社区之间的流距离。然后，取两个彼此连接且流距离最短社区进行合并，重新计算社区之间的距离，如此不断迭代，直到所有的节点都被放入同一个社区。这个过程社区的数目不断减小，导致出现一个树图分层（dendrogram）结构。在这个过程中，可以使用Q-modularity的变化来指导搜索的方向。

[]标签扩散算法label propagation

这种算法的思路源于冯诺依曼在50年代提出的元胞自动机模型（cellular automata）和Bak等人在2002年左右做的沙堆模型。该算法的基本原理如下：首先，给全网每个节点分配一个不重复的标签（label）；其次，在迭代的每一步，让一个节点采用在它所有的邻居节点中最流行的标签（如果最佳候选标签超过一个，则在其中随机抽一个），；最后，在迭代收敛时，采用同一种标签的节点被归入同一个社区。这个算法的核心是通过标签的扩散来模拟某种流在网络上的扩散。其优势是算法简单，特别适用于分析被流所塑造的网络。在大多数情况下可以快速收敛。其缺陷是，迭代的结果有可能不稳定，尤其在不考虑连边的权重时，如果社区结构不明显，或者网络比较小时，有可能所有的节点都被归入同一个社区。

[]流编码算法 the Map Equation

Rosvall和Axelsson 2009年提出了一种很有意思的方法来研究网络中的流动。其核心思想是，好的社区划分要令网络上流的平均描述长度最短。他们认为，分析有向加权网络的一个好的视角是观察某类实体（货币、能量、信息）在网络上的流动。即使没有实体流动的数据，我们也可以根据网络的基本结构来推测随机游走的粒子的轨迹，然后对得到的“平均流”进行信息编码。对“平均流”的描述长度最短的编码机制，就对应着对社区的一种最有效划分。

首先要讨论的是节点层编码。最简单的方式是给每个节点分配一个独特的二进制签名。但这种编码方式并不高效，因为节点被访问的概率并不一样。为了改进，我们可以引入一个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被使用）。

在这个两层编码体系中，包括三类码表（code book）。第一个是主码表（master code book），决定每个社区的编码；第二个是传送门码表（exit code book），决定每个社区的出口连边的编码；第三个是节点码表（node code book），决定每个社区内的节点的编码。一旦对网络的社区划分P（partition）给定，就存在一个社区码表，一个传送门码表，和m个节点码表，其中m是社区的个数。最后，社区划分的目标就是要最小化所有码表的总长，或者按论文中的说法，平均随机游走中的一步所耗费的信息成本。这个思路以一种很有趣的方式利用了网络社区的定义。网络社区的存在，意味着社区内的流动较多，跨越社区的流动较少。因此，一个好的社区划分意味着主码表和传送门码表被调用的次数都很少，描述的信息配额（quota）主要用于描述社区内的流动。相反，如果待分析的是一个随机的网络，或者研究者构造了一种低效的社区划分，那么主码表和传送门码表被调用的次数将会很多。特别是传送门码表，也就是错误的社区划分会大大加大这个码长。

一个总结了以上思想的公式可以表达如下，作者称之为the map equation。

其中M即对网络的某种社区划分得到m个社区。L是该划分所对应的信息描述长度。qi->代表进出第i个社区的概率（先考虑无向网络），因此q->代表社区间跳转的总概率。H(Q)是社区间跳转行为的香农信息量。Pi->代表第i 个社区内节点间跳转的总概率，H(Pi)是第i个社区内节点间跳转行为的香农信息量。在公式的两个部分，信息量都用其被使用的频率进行加权。经过展开化简，可以得到简化形式如下：

最后，使用某种社区划分的搜索策略（主要有细分与合并两种）来寻找该描述长度的最小值即可。值得注意的是，在实际计算中，节点层的信息量（第三项）是不需要考虑的。

[]流层级算法 Role-based Similarity

Cooper和Barahona 在2010年提出了一个算法，可以揭示网络中流的层级关系。他们认为，通过对网络的邻接矩阵A进行分析，可以得到一个节点从一步到k步的出流或入流的画像（flow profile），在任意两个节点之间比较这种流画像，就可以得到节点之间的相似性，从而为社区划分服务。

具体过程如下：先得到网络的邻接矩阵A，这个时候V=AKI中的元素Vi就代表第i个节点在k步的所有出流之和。类似地，U=(AT)KI中的元素Ui就代表第i个节点在k步的入流之和。

如公式所示，我们可以构造n * k的矩阵Xin，其元素Xinij代表第i个节点在第k步的入流；也可以构造Xout，其元素Xoutij代表第i个节点在第k步的出流。把Xin和Xout横着拼在一起，就是X。其维度为n * 2k。在X矩阵上，第i行正好描述了节点i在k步内的所有入流和出流的信息。因此，可以通过计算第i行和j行的Cosine 距离或者Manhattan距离等来定义节点相关性rij，最后得到的相关性矩阵，就可以用于聚类。

图3展示了将role-based similarity方法用于分析一个示例流网络的结果。发现分类的结果确实反映了流的层级关系。值得注意的是，虽然在论文中作者建议使用Cosine距离，但我发现在这个实例网络上，使用Manhattan距

离的结果能更清晰地揭示流层级结构。因此，具体的分析要看数据的情况，这也是应用这种算法需要考虑的局限之一。

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

欢迎您的下载，

资料仅供参考！

致力为企业和个人提供合同协议，策划案计划书，学习资料等等

打造全网一站式需求

一种新的基于标签传播的重叠社区发现算法

一种新的基于标签传播的重叠社区发现算法 摘要摘要：发现高质量的社区是社区网络问题的研究热点。目前，社区发现算法大多针对非重叠社区，重叠社区发现算法较少。基于标签传播的算法是现有重叠社区发现算法中的一类，其中COPRA为典型算法。尽管该算法具有接近线性的时间复杂度，但存在随机因素，结果不稳定，产生的社区结构存在一定差异。为此，提出一种新的基于标签传播的社区发现算法，实验表明该算法在复杂度相近的情况下能明显提高所发现社区的质量，且具有较好的稳定性。 关键词关键词：社区发现；重叠社区；标签传播；稳定性 DOIDOI：10.11907/rjdk.1431038 中图分类号：TP312 文献标识码：A文章编号 文章编号：16727800（2015）004005904 1重叠社区及其发现算法 近年来，复杂网络研究受到广泛关注，主要涉及系统科学、统计物理学、社会科学、生物学等多个领域[1]。随着通信和互联网技术的快速发展，人们发现众多网络都存在社区结构[2]这一特征。所谓社区结构，简单来说，就是网络中的

节点存在分组，一般组内的边连接比较稠密，而组间的边连接比较稀疏。社区结构在一定程度上可以反映出真实网络的拓扑关系。社区发现可以帮助更好地理解网络拓扑结构及其功能，从而更好地利用和改造网络，例如挖掘网络中的未知功能、控制疾病传播等。社区发现在某些特定应用环境中也有现实意义，例如发现恐怖分子、寻找犯罪团体等。 然而，真实网络存在一些同时属于多个社区的节点，这些节点叫作“重叠节点”，与其它社区存在重叠节点的社区就叫作“重叠社区”。例如在社会关系网络中，小王既参加了台球俱乐部，又参加了乒乓球俱乐部，那么小王就是这两个社区的重叠节点，台球俱乐部和乒乓球俱乐部是两个重叠社区。重叠社区较之非重叠社区具有更好的现实意义：一方面，重叠节点是网络中关键点，重叠社区因此而产生联系；另一方面，重叠社区反映了更加真实的网络结构。因此，研究重叠社区更符合真实网络的结构。 图1为非重叠社区结构，图2为接近真实网络的重叠社区结构。目前，能够发现重叠社区结构的算法主要包括以下3类： （1）基于clique的方法。典型算法有CPM算法[3]、EAGLE算法[6]和GCE算法[7]。 （2）基于合并社区核心和扩展社区的方法[8]。 （3）基于标签传播的方法典型算法有LPA算法[4]和

网络社区划分算法

网络社区划分算法 目录 ? 1 简介 ? 2 构建一个点击流网络 ? 3 网络社区划分的两种主要思路：拓扑分析和流分析 ? 4 拓扑分析 o 4.1 计算网络的模块化程度Q-Modularity o 4.2 计算网络的连边紧密度Edge betweenness o 4.3 计算网络拉普拉斯矩阵的特征向量Leading eigenvector o 4.4 通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值 o 4.5 通过multi level方法搜索网络模块化程度Q-Modularity的最大值 ? 5 流分析 o 5.1 随机游走算法Walk Trap o 5.2 标签扩散算法label propagation o 5.3 流编码算法 the Map Equation o 5.4 流层级算法 Role-based Similarity ? 6 总结 使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。 假设我们手头有一批用户在一段期间访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（user visit）排名前V的资源，得到节点集合|V|，然后对于一个用户i在一段时间（例如一天）访问的资源，选择属于|V|的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。对于一天的n个用户做这个操作，最后将得到的总数为的连边里相同的边合并，得到|M|个不同的边，每条边上都带有权重信息。这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。

我国四大地理区域的划分教学设计说明

《我国四理区域的划分》教学设计 一、教材分析： 本章容是中国地理总论部分和中国地理区域部分的衔接点。本节容主要分为两个部分：岭—淮河线，四理区域。根据《地理课程标准》要求，本节容要求第一知道“岭-淮河”的位置，通过“比较”活动认识岭南北两侧的自然差异，理解岭-淮河线的地理意义。第二明确“四理区域”各区的围和划分依据，通过“比较”活动揭示各个地理区域之间的差异。 本节的教学就是要把学生对区域差异的感性认识上升到理性的程度，理解区域划分的作用，掌握区域划分的基本方法，学会通过比较的方式了解我国的宏观区域差异。可从生活实例出发，认识区域划分的方法，并增强学生学习的兴趣 二、教学对象分析： 1、地理学习能力：七年级学生通过一年半学期的地理学习，学生已经有了一定的地理习惯，已基本掌握了地理读图、看图的方法，具有一定绘图能力，能通过自主探究初步完成老师的问题；但学生整体的分析、归纳能力，仍然较弱，比较依赖老师或优生分析解答。因此在地理教学过程中，要不断引导他们思考、分析、归纳。通过“提问—探究—小结”来完成学习任务。目前学生有了一定的读图能力，析图能力和解决问题的能力，能自主探究完成老师的问题，为学习本节课提供了能力基础。 2、知识水平：经过一个半学期的地理学习，学生对我国的自然环境情况，行政区域划分，经济概况，已有了初步的认识，为学好我国四理区域的划分，奠定了知识基础。 3心理特性：七年级学生兴趣较浓，求知欲较强，思维活跃，课堂参与意识较强，喜欢表现自己，集体荣誉感强，部学生具有良好的创新意识和创新能力，为本课学习奠定了情感基础。 三、教学目标： 知识目标：1、岭、淮河一线，说明岭—淮河一线的地理意义。 2.在地图上指出四大区域的地理位置、围及划分原因以及地理差异； 能力目标：能够读图查找地理界线，通过读图讨论分析问题，归纳知识点。 情感目标：让学生关注家乡所在地区的区域特征，找出与相邻地区的差异。 四、教学的重点和难点： 重点:我国四理区域的位置、围及划分原因。 难点:四理区域的差异。 五、教学策略： 指导学生读图、析图，观察判断和主动探究。基于本节课空间分布思维的特点和学生本身对四理区域的自然景观等没有基本的认识，故主要运用powerpoint课件，结合导学案采用多媒体教学法，集图片、图表于一身，变抽象为形象。教学方法：采用读图分析法、自主探究学习、小组合作学习。 六、.教学准备： （1）教师准备：绘制简易“中国四理区域图”，准备地区景观图片，导学案。 （2）学生准备：七年级下册课本、地图册、彩笔。 七、教学过程：

大型复杂网络中的社区结构发现算法

—92— 大型复杂网络中的社区结构发现算法 胡 健1，董跃华1，杨炳儒2 (1. 江西理工大学信息工程学院，赣州 341000；2. 北京科技大学信息工程学院，北京 100083) 摘 要：在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值。该文把超图模型以及基于此的聚类算法应用到社区结构发现的领域。对于简单图的社区结构发现，引入边聚集系数的概念，提出基于边聚集系数的社区发现算法。将安然邮件数据集作为测试数据集，通过算法对比分析，证明该算法在时间复杂度上可以提高一个数量级。 关键词：边聚集系数；社区结构；社区发现 Community Structure Discovery Algorithm in Large and Complex Network HU Jian 1, DONG Yue-hua 1, YANG Bing-ru 2 (1. Faculty of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000; 2. School of Information Engineering, University of Science and Technology Beijing, Beijing 100083) 【Abstract 】The automatic search and community discovery in large and complex network has important practical applications. This paper applies the hypergraph based model and cluster algorithm in community structure discovery, introduces the concept of Edge Clustering Coefficient(ECC) to community structure discovery of simple graph and proposes an algorithm of community discovery based on ECC. Enron e-mail data sets are test data sets, through comparative analysis of algorithm, to prove that this algorithm can significantly improve the time complexity. 【Key words 】Edge Clustering Coefficient(EBB); community structure; community discovery 计 算 机 工 程Computer Engineering 第34卷 第19期 Vol.34 No.19 2008年10月 October 2008 ·网络与通信· 文章编号：1000—3428(2008)19—0092—02 文献标识码：A 中图分类号：TP301.6 1 概述 复杂网络中社区发现(community finding)的研究起源于 社会学的研究工作。能够在大型复杂网络中自动搜寻或发现“社区”具有重要的实际应用价值[1]，如社会网络中的社区可能代表的是根据兴趣或背景而形成的真实的社会团体，引文网络中的社区或许代表的是针对同一主题的相关论文，万维网中的社区或许就是讨论相关主题的若干网站，而生物化学网络或者电子电路网络中的社区可能就是某一类功能单元。发现这些网络中的社区有助于更有效地理解和开发这些网络。与社区发现相关的成熟理论包括图论以及模式识别。Wu 和Huberman 的研究成果[2]以及Newman 和Girvan 的研究成果[3]使得复杂网络中的社区发现成为近几年复杂网络领域的一个研究热点并形成了复杂网络中的一个重要研究方向。Newman 和Girvan 把社区发现问题定义为将网络节点划分成若干组，使得组内的节点之间连接比较稠密而不同组节点之间的连接则比较稀少。Newman 和Girvan 在其研究中提出了基于边介数(edge betweenness)概念的分割方法，尽管该方法计算量很大，但由于其性能优越而成为社区发现研究的重要参考模型。 对于一般简单图的社区发现，也可以称之为基于图的聚类，把具有相同或者相似属性的有共性的节点聚合到一起，形成一个个的聚类[2]。这方面的方法有很多，最常用的有G-N 算法、谱二分法和层次聚类法。 尽管人们对复杂网络的社区发现问题已进行了大量的研究，但是仍然存在一些目前无法解决的基本问题[4]，如社区的概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需要的计算量却很大；更为 关键的是，很多算法不是针对异构数据集。这说明复杂网络中社区发现的研究还远没有成为体系，还有很多工作待完善。 2 边的聚集系数定义 为了刻画描述一个网络，通常有这样几个角度，一个是这个网络中点与点之间的距离以及整个网络的平均距离；另一个是每个节点的度以及整个网络的平均的度；还一个就是节点之间聚集的情况，点的聚集系数这个概念是用来体现对于某个节点A 来讲，如果B 和C 都是A 的邻接点(朋友关系)，那么B 和C 两者之间也有邻接(朋友)的可能性。 定义1 某节点n 的聚集系数(node clustering coefficient) ()C n 如下定义： (1)假设某节点n 的度是k ，则该节点的这些邻居之间可能形成边的最大数是： ()(1)/2T n k k =? (2)()E n 表示图中这些邻居之间实际的边的个数，则 ()()/()C n E n T n = 定义2 一个网络的聚集系数为这个网络中节点的聚集系数的平均值。 如图1所示，节点1的度为5，所以与它相连接的5个顶点之间最多存在54/210×=条边；而实际上另外5个顶点相互之间存在6条边，所以节点1的聚集系数是6/100.6=。 基金项目：国家自然科学基金资助项目(60675030) 作者简介：胡 健(1967－)，男，副教授、博士，主研方向：数据挖掘，智能信息检索；董跃华，副教授；杨炳儒，教授、博士生导师 收稿日期：2008-08-01 E-mail ：euguenehu@https://www.docsj.com/doc/8816760645.html,

网络社区划分方法及评价

网络社区划分方法及评价 【摘要】网络社区结构是社会网络最普遍和最重要的拓扑属性之一，其特点是，同一社区内的节点连接密集，不同社区间的节点连接稀疏。揭示网络社区结构对分析复杂网络拓扑结构、理解其功能、发现其隐含模式、预测其行为都具有十分重要的理论意义，在社会网、生物网和万维网中具有广泛应用。本文主要从网络社区划分的起源、常见的社区划分方法及社区评价准则等三个方面介绍网络社区划分研究的相关工作。 【关键词】复杂网络；网络社区；社区划分；社会网络分析；社区的评价；局部社区划分 0.引言 网络科学将系统内部的各个元素作为节点，元素之间的关系视为连接，那么系统就构成了一个具有复杂连接关系的网络。然而，近几年的实证研究表明，这些看似毫不相干的且形态各异的真实系统的拓扑抽象都具有某些共同的拓扑性质，如小世界与无标度特性等等。由于它们所表现出来的拓扑性质与随机网络、规则网络等有着天壤之别，且节点众多，因此被称为复杂网络。目前，复杂网络成为技术、生物乃至社会各类复杂系统的非常一般的抽象方法与描述骨架，相关研究成为重要的学科交叉研究前沿。 所谓社区(community)即指网络的内聚子图，其基本特征表现为子图内部链接丰富，不同子图之间连接相对稀少。 1.常见网络社区划分方法 1.1基于优化思想的算法 基于优化思想的算法将复杂网络社区划分转化为优化问题，通过最优化预定义的目标函数来计算复杂网络的社区结构。比如K-L算法、谱平分法、随机游走(Random Walks)算法和派系过滤(CMP)算法等。这些算法的突出优点是速度比较快，效率显著。但是缺点也很突出，这一类算法都需要知道网络社区的数目，甚至KL算法还需要知道每个社区中各有多少节点，才能正确划分。这显然不适于网络未知社区的探索。 1.2社会网络分析方法 源于社会网络分析中寻找社区结构的传统算法，主要基于分级聚类思想，按照各个节点之间连接的相似性或者强度，把网络自然地划分为各个子群。其具体实现方式又有两种：其一是往网络中添加边，即凝聚方法(agglomerative method)；其二是又从网络中移除边，即分裂方法(divisive method)。凝聚方法的基本思想是基于网络中节点某种相似性分层进行聚类的。初始时，每个节点为一个社区，然

八年级地理下册第五章《中国四大地理区域划分》获奖教案

【课题】八下第五章中国四大地理区域划分 【课型】新授课 【课标要求】 1．运用地图说出我国四大地理区域的名称、范围及划分的依据2．在图中指出秦岭、淮河，并说明秦岭-淮河一线的地理意义。 3. 结合本节课的学习，说说自己对家乡自然地理环境的认识。【教学目标】 【教学方法】小组讨论法读图分析法 教学环节教师活动学生活动设计 意图 导入新课 【导入】：首先，我们看看下列几幅 图各是哪个地区的景观： 教师引言：我国幅员辽阔，地域差 异显著，从雪山连绵的青藏高原，到麦 浪滚滚的华北平原，从牛羊成群的内蒙 学生观察图片，结合日 常所见所闻试着说出图中的 四个地区： 依次是西北地区、华北平原、 南方地区、内蒙古高原。 仔细阅读教学目标，快速浏 览本节内容。 图片直 观性强， 学生在 观察图 片的同 时体会 祖国大 地的姿 态万千。1．运用地图指出北方地区、南方地区、西北地区和青藏地区四大地理区域的范围，明确四大地理区域划分的依据。 2. 在地图上找出秦岭、淮河，并说明秦岭——淮河一线的地理意义。 3. 试着评价家乡的自然地理环境。

合作探究古高原到浩瀚无垠的新疆沙漠、戈壁 滩，祖国大地姿态万千，风光无限。 【教学目标】： ?运用地图指出北方地区、南方地 区、西北地区和青藏地区四大地理区域 的范围，明确四大地理区域划分的依 据。 ?在地图上找出秦岭、淮河，并说明 秦岭——淮河一线的地理意义。 一、中国的四大地理区域的划分 观察分析：1、四大分区的地理界线是 如何确定的？（在下面的图中找出秦岭 -淮河一线、400毫米等降水量线和青藏 高原边缘线，与中国四大地理区域界线 对应起来） 读图分析，找出找出秦岭- 淮河一线、400毫米等降水 量线和青藏高原边缘线，与 中国四大地理区域界线作一 比较。 组内交流，学生代表回答观 察的结果：秦岭-淮河一线基 本与1月0℃等温线、800 毫米等降水量线一致；西北 地区和北方地区的界线基本 与季风区和非季风区一致； 青藏地区与其他地区的分界 线基本与一二级阶梯分界线 一致。 学会读 图是学 好地理 的关键， 等温线 图和等 降水量 线图以 及分层 设色地 形图，都 是以往 所学，学 生可以 将新旧 知识结 合，增强 知识的 联系性。

复杂网络社区发现若干问题研究

复杂网络社区发现若干问题研究 近年来,复杂网络逐渐成为信息科学、社会学、物理学、乃至生命科学等学科研究的热点。所谓复杂网络,是指将自然界中的各个实体抽象为网络中的节点,实体与实体之间的关系抽象为网络中的边。 这使得自然界中的很多系统都可以表示为复杂网络的形式,例如社会关系网、科学家合作网、通信网、互联网、人类疾病基因网等等。研究发现,复杂网络具有复杂的内部结构和多样的结构特征,其中,模块性(即社区结构)是复杂网络的 一个重要特征,它表现出网络中的节点具有聚集化的特性,即社区内部节点之间 连接稠密、社区之间的节点连接稀疏。 此外,社区结构在现实世界中往往是“重叠”的。复杂网络(重叠)社区结构的发现对于分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律以及预测复杂网络的行为具有十分重要的意义。 目前,研究者提出了众多网络(重叠)社区发现方法,并将之成功应用于现实 系统的分析中,然而社区发现方法存在的问题还有很多,如复杂网络社区发现问 题与聚类分析问题两者之间的关系还有待研究；网络社区发现算法尤其是重叠社区发现算法的精度和效率还有待提高；传统的划分评价函数模块化Q函数存在分辨率的限制等等。鉴于复杂网络社区发现问题与传统机器学习中的聚类分析问题都是对数据进行划分,并且机器学习中的聚类分析研究日趋成熟,本文结合机器 学习相关的技术和方法,改进并提出了若干发现网络(重叠)社区的算法,主要贡 献如下：(1)揭示了社区发现问题和聚类分析问题之间的区别和联系,利用聚类分析中定义的相似度概念对GN (Girvan and Newman)算法进行改进,给出了快速的SGN (GN based on similarity)算法。

网络社区划分算法

网络社区划分算法 目录 ?1简介 ?2构建一个点击流网络 ?3网络社区划分的两种主要思路：拓扑分析和流分析 ?4拓扑分析 o 4.1计算网络的模块化程度Q-Modularity o 4.2计算网络的连边紧密度Edge betweenness o 4.3计算网络拉普拉斯矩阵的特征向量Leading eigenvector o 4.4通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值 o 4.5通过multi level方法搜索网络模块化程度Q-Modularity的最大值 ?5流分析 o 5.1随机游走算法Walk Trap o 5.2标签扩散算法label propagation o 5.3流编码算法 the Map Equation o 5.4流层级算法 Role-based Similarity ?6总结 []简介 使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。 假设我们手头有一批用户在一段期间内访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（user visit）排名前V的资源，得到节点集合|V|，然后对于一个用户i在一段时间内（例如一天）内访问的资源，选择属于|V|的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。对于一天内的n个用户做这个操作，最后将得到的总数为的连边里相同的边合并，得到|M|个不同的边，每条边上都带有权重信息。 这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。

基于核心节点的社区发现算法

文献引用格式:冯译萱?张月霞.基于核心节点的社区发现算法[Ｊ].电视技术?２０１９?４３(１):１１－１６. ＦＥＮＧＹＸ?ＺＨＡＮＧＹＸ.Ｃｏｍｍｕｎｉｔｙｄｉｓｃｏｖｅｒｙａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｃｏｒｅｎｏｄｅｓ.ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ [Ｊ].Ｖｉｄｅｏｅｎｇｉｎｅｅｒｉｎｇ?２０１９?４３(１):１１－１６. 中图分类号:ＴＰ３９１一一一一文献标志码:Ａ一一一一ＤＯＩ:１０.１６２８０/ｊ.ｖｉｄｅｏｅ.２０１９.０１.００３ 基金项目:国家自然科学基金(Ｎｏ.５１３３４００３?Ｎｏ.６１４７３０３９) 基于核心节点的社区发现算法 冯译萱?张月霞 (北京信息科技大学一信息与通信工程学院?北京一１００１０１) 摘要:针对基于全局的社区发现方法计算复杂度较高?基于局部的社区发现方法难以保证划分准确度的问题?本文提出了一种基于核心节点的社区发现算法?通过局部聚类系数和度计算网络中节点的优先级?以便更准确的选取核心节点?利用多层节点相似度判断其他节点与核心节点是否可以划分进同一小团体?可以提高节点划分准确性?最后?将紧密程度较大的小团体进行合并?得到划分结果?本文在真实的网络上进行验证?与ＧＮ算法和ＦＮ算法相比?本算法具有更好的划分准确性? 关键词:社区发现?节点相似性?复杂网络?核心节点 Ｃｏｍｍｕｎｉｔｙｄｉｓｃｏｖｅｒｙａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｃｏｒｅｎｏｄｅｓ.ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ ＦＥＮＧＹｉｘｕａｎ?ＺＨＡＮＧＹｕｅｘｉａ (ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＣｏｍｍｕｎｉｃａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ?ＢｅｉｊｉｎｇＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ＆ＴｅｃｈｎｏｌｏｇｙＵｎｉｖｅｒｓｉｔｙ?Ｂｅｉｊｉｎｇ１００１０１?Ｃｈｉｎａ) Ａｂｓｔｒａｃｔ:Ｉｎｏｒｄｅｒｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｔｈａｔｔｈｅｃｏｍｍｕｎｉｔｙｄｉｓｃｏｖｅｒｙｍｅｔｈｏｄｂａｓｅｄｏｎｔｈｅｇｌｏｂａｌｃｏｍｍｕｎｉｔｙｄｉｓｃｏｖｅｒｙｉｓｍｏｒｅｃｏｍｐｌｅｘａｎｄｔｈｅｌｏｃａｌｃｏｍｍｕｎｉｔｙｄｉｓｃｏｖｅｒｙｍｅｔｈｏｄｉｓｄｉｆｆｉｃｕｌｔｔｏｅｎｓｕｒｅｔｈｅａｃｃｕｒａｃｙｏｆｔｈｅｃｏｍｍｕｎｉｔｙｄｉｓｃｏｖｅｒｙ?ａｃｏｍｍｕｎｉｔｙｄｉｓ￣ｃｏｖｅｒｙａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｃｏｒｅｎｏｄｅｉｓｐｒｏｐｏｓｅｄｉｎｔｈｉｓｐａｐｅｒ.Ｔｈｉｓｐａｐｅｒｃａｌｃｕｌａｔｅｓｔｈｅｐｒｉｏｒｉｔｙｏｆｎｏｄｅｓｉｎｔｈｅｎｅｔｗｏｒｋｂｙｌｏ￣ｃａｌｃｌｕｓｔｅｒｉｎｇｃｏｅｆｆｉｃｉｅｎｔａｎｄｄｅｇｒｅｅ?ｓｏａｓｔｏｓｅｌｅｃｔｔｈｅｃｏｒｅｎｏｄｅｓｍｏｒｅａｃｃｕｒａｔｅｌｙａｎｄｄｅｔｅｒｍｉｎｅｗｈｅｔｈｅｒｏｔｈｅｒｎｏｄｅｓａｎｄｃｏｒｅｎｏｄｅｓｃａｎｂｅｄｉｖｉｄｅｄｉｎｔｏｔｈｅｓａｍｅｓｍａｌｌｇｒｏｕｐｂｙｔｈｅｓｉｍｉｌａｒｉｔｙｏｆｍｕｌｔｉ－ｌａｙｅｒｎｏｄｅｓ?ａｎｄｔｈｅａｃｃｕｒａｃｙｏｆｔｈｅｎｏｄｅｐａｒｔｉｔｉｏｎｃａｎｂｅｉｍｐｒｏｖｅｄ.Ｆｉｎａｌｌｙ?ｔｈｅｓｍａｌｌｇｒｏｕｐｓｗｉｔｈｌａｒｇｅｒｔｉｇｈｔｎｅｓｓａｒｅｍｅｒｇｅｄ?Ｔｈｅｒｅｓｕｌｔｏｆｄｉｖｉｓｉｏｎｉｓｏｂｔａｉｎｅｄ.Ｔｈｉｓａｌｇｏｒｉｔｈｍｉｓｖｅｒｉ￣ｆｉｅｄｉｎｒｅａｌｎｅｔｗｏｒｋ.ＣｏｍｐａｒｅｄｗｉｔｈＧＮａｌｇｏｒｉｔｈｍａｎｄＦＮａｌｇｏｒｉｔｈｍ?ｔｈｉｓａｌｇｏｒｉｔｈｍｈａｓｂｅｔｔｅｒｐａｒｔｉｔｉｏｎａｃｃｕｒａｃｙ. Ｋｅｙｗｏｒｄｓ:Ｃｏｍｍｕｎｉｔｙｄｉｓｃｏｖｅｒｙ?Ｎｏｄｅｓｉｍｉｌａｒｉｔｙ?Ｃｏｍｐｌｅｘｎｅｔｗｏｒｋ?Ｃｏｒｅｎｏｄｅ １一前言 现实中?大量的复杂系统可以描述成网络形式? 如社交网络二病毒传播网络二互联网络二科学家合作 网络等等?这些复杂网络通常具有小世界特性和无 标度特性?研究发现?绝大多数的复杂网络的拓扑 结构都具有总体分散二局部聚类的特征?这种特征称 为社区结构[１]?社区内部节点连接紧密?社团间连 接较为稀疏?同一社区内的节点属性相近?社区发 现算法可以通过分析网络中节点的关系?对于挖掘 网络中的拓扑结构?从而预测网络行为具有重要 意义[２]? 目前存在很多种社区发现方法?主要包括三类: 基于全局的社区发现方法二基于局部的社区发现方 法和基于结构相似度的社区发现方法[３]?(１)基于 全局的社区发现方法是从网络整体出发?通过某个 性质划分出网络中的社区?包括图划分[４]二模块度优 化[５－６]二层次聚类[７]以及基于图模型[８]的方法等? 但实际网络规模庞大二数据动态增长?此时使用全局 方法?计算复杂度高二并行处理效率低?而且从全局 结构进行划分难以体现出局部社区的结构重叠特 征?(２)基于局部的社区发现方法一般选取网络中 的一个或几个初始节点进行社区结构的条件划分? 并找出网络中满足条件的极大子网络?这些子网络

中国四大地区划分

四大地理区域的划分北方地区和南方地区 主讲：占汛 一周强化 一、一周内容概述 （一）四大地理区域的划分 1、不同的地理区域 2、我国的四大地理区域 （二）北方地区和南方地区 1、北方与南方的自然差异 2、北方与南方的人文差异 二、重难点讲解 （一）四大地理区域的划分 1、不同的地理区域

上图通过四个人物分别描述自己生活地理区域的显著特征，形象直观地说明地理区域的差异性。 第一位身着维吾尔族服装表明“新疆维吾尔自治区”是我国一级行政区划中五个少数民族自治区之一；“山地上有大面积的草场”描述出自然环境情况；而高山牧场成为“我国有名的牧区”，表现出畜牧业是本区经济发展中的重要部门。 第二位来自西双版纳傣族自治州，该地位于云南省，属二级行政区划单位；傣家少女服饰表明这里也是少数民族的聚集区；“位于热带，气候湿热”，点出那里具有的热带气候特征；“美丽、旖旎的风光”、典型的热带景观和独特的傣家风情，不难得出结论，旅游资源的开发，会大大促进本区经济的发展。 第三位家住东南沿海地区，“经济发展很快”说明本区位于我国东部经济较为发达的地区，“经济特区”是根据本区对外开放的需要再划分的特殊经济区。 第四位来自长江三角洲，是个自然地理区域，由于自然条件的优越，农业发展历史悠久，在良好的农业基础上，又形成实力雄厚的工业区。 地理区域不仅可以划分为多种类型（自然区域、经济区域、行政区域），而且同一类型的区域，还可以划分出不同尺度或不同级别的区域（如：行政区域：省、县、乡；再如：温度带：热带、亚热带、温带（暖温带、中温带、寒温带）。 2、我国四大地理区域

我国疆域辽阔，不同地区的地理环境差异很大。根据各地的地理位置、自然和人文地理特点的不同，可以将我国划分为四大地理区域：北方地区、南方地区、青藏地区、西北地区。 北方地区与南方地区分界线是秦岭——淮河一线，即1月0℃等温线和800mm等降水量线。划分的主导因素是气温和降水因素（气候因素）。

二部图社区划分算法的实现与验证

二部图社区划分算法的实现与验证 2015年6月

摘要 二分网络是复杂网络的网络表现形式之一，二部图是描述二分网络的工具。对于二分网络的社区划分研究通常用以下方法：一种方法是把二分网络以无权投影或加权投影的方式投影到单分网络中进行社区划分。但是这种方法有个缺点：它会把原始二分网络上的一部分信息丢失，导致实验结果不准。另一种方法是直接在二分网络上进行网络社区划分，这种方法很好的避免了上一种方法中投影造成的实验误差。 PageRank算法是Google的网页排序算法，是Google用来衡量网页的重要性的算法，该算法根据人们对这个网页的点击率来衡量网页的受欢迎程度从而得出该网页的排序，该算法是随机游走理论的一个典型应用模型。 对二分网络单侧节点进行社区划分的研究是具有重要的实际意义的。基于能量在网络中的转移概率和模块度思想，本文将PageRank算法用于二分社交网络的社区发现中，具体内容是利用二分社交网络节点间的连接关系，构造PageRank算法适用的概率转移矩阵，并利用不同维度的两个PageRank矩阵的联合运算，实现对二部图中单侧节点的社区划分，并计算出Q值。该算法通过模拟能量在网络中转移的过程，利用各个节点的能量在网络中转移后收到的其他节点的能量作为社区之间合并的依据，并用模块度作为判断社区划分好坏程度的标准。最后将PR算法用于典型网络（南非妇女网络）上测试。 关键词：二分网络；PR算法；模块度；随机游走理论；社区划分

Abstract Bipartite network is one form of the network performance in complex networ- ks,bipartite figure is a tool of describing bipartite network.For the research of bipartite net- work community division,there are usually two ways.One way is to divide the bipartite network into the one-mode network in the form of a unweighted projection or weighted projection for community division.However,this method come with a disadvantage:it will lose some information of the orginal bipartite network,which leads to the experimental results inaccurate.Another way is to divide the network community directly on the bipartite net- work.This method can avoid the error caused by the first method. PageRank algorithm is a page ranking algorithm which Google used to measure the importance of web page algorithm.It can measure webpage popularity according to the web hits and get the page ranking.This algorithm is a typical application model of random walk theory. The research on the community division of the unilateral nodes in bipartite network has very important practical significance.Based on energy transfer probability in the network and modularity thought,this article use PageRank algorithm for bipartite social network community discovery,specific content is using the bipartite social connection relationship between network nodes to construct the probability transfer matrix for PageRank algorithm.By using different dimensions of two PageRank matrix for compu- tation to realize the unilateral nodes in the bipartite figure community division and cal- culate Q value.This algorithm simulate the energy transfer process in the network,take the energy of each node in the network transfer energy received after other nodes as the basis of merger,use modularity as the judgement of community division.At last,the PageRank algorithm is used for testing in the typical network(south Africa women’s network). Keywords: bipartite network; PR algorithm; modularity; random walk theory; community division

中国的四大地理区域的划分2

八（下）地理第一节中国四大地理区域的划分练习题1 秦岭-淮河线以北秦岭-淮河线以南 1月平均气温<0o C ________ 河流封冻状况________ 不封冻 年降水量<800毫米________ 植被类型_________________为主亚热带常绿阔叶林为主耕地类型_________为主___________为主 主要粮食作物________、玉米________ 作物熟制 一年两熟、 两年三熟或一年一熟 一年两熟到三熟 主要经济林木苹果、柿、枣柑橘、茶叶、油桐主要运输方式____________ 公路、铁路、水运 1、AB线是我国的一条重要地理界线，该线是（） A.青藏高原边缘线 B.秦岭-淮河一线 C.地势第一、二级阶梯分界线 D.地势第二、三级阶梯分界线 2、下图中能反映丙．地区气候特点的是（） 3、读右图，图中秦岭-淮河线构成了我国重要的地理分界线，不．属于该线的是（） A.800mm年等降水量线 B.1月份0o C等温线 C.季风区和非季风区的分界线 D.旱地、水田分界线 4、下列数据中，有可能为正常年份A地1月份平均气温的是（） A. 5o C B. 8o C C. -4o C D. 16o C 5、我国四大地理区域中，西北地区与北方地区界限的划分主要受什么因素的影响（） A.纬度位置 B.夏季风的影响 C.地形地势 D.农业生产方式的不同 6、下列各省级行政区中，位于秦岭-淮河 线以北的是（） 7、确定西北地区与北方地区界线的主导因 素是（） A.气温 B.降水 C.地形 D.地势 8.下图为第五套人民币上所显示的地理景 点，两处景点所在地理区域分别是（） A.南方地区、北方地区B．南方地区、青藏地 区C．西北地区、南方地区D．北方地区、青 藏地区 9.下列山脉不属于南方地区的是( )。 A．巫山 B．南岭 C．武夷山D．太行山 10.导致我国南方和北方耕作制度产生很大差异的主要因素是( )

局部最优社区挖掘算法(社区紧密度,关键词查找)

收稿日期:2008-11-07;修回日期:2009-01-15 基金项目:国家“863”重点基金资助项目(2006AA010106);国家“973”基金资助项目(2007C B311007) 作者简介:吴龙庭(1982-),男,湖北荆州人,博士研究生,主要研究方向为信息检索、决策科学(aaron792@https://www.docsj.com/doc/8816760645.html,);戴汝为(1932-),男,院士,主要研究方向为人工智能、模式识别;崔霞(1975-),女,副研究员,博士,主要研究方向为信息检索、人工智能. 一种局部最优社区挖掘方法 * 吴龙庭,戴汝为,崔 霞 (中国科学院自动化研究所复杂系统与智能科学重点实验室,北京100190) 摘 要:研究互联网论坛中划分用户社区问题。首先通过分析用户在论坛上的发言层次结构与内容建立用户之间的回复关系图,然后提出一种基于局部最优的图聚类方法LOGCA 对大容量的论坛网络图进行分类。实验得到互联网论坛上几个有意义的用户社区,并且确定了社区成员的共同兴趣。实验结果表明新方法简单有效,能够从大规模网络中发掘出有意义的用户社区。关键词:社会网络;知识发现;数据挖掘;中文论坛 中图分类号:TP 391 文献标志码: A 文章编号:1001-3695(2009)08-2855-03doi:10.3969/j.issn.1001-3695.2009.08.014 Com m unity m ining approach ba sed on local opt im izat ion WU Long-t ing,DAI Ru-wei,C UI Xia (K ey Laboratory of Complex Sys tem &Intelligence S cience,Institute of Automation,Chinese Academy of Sciences,B eijing 100190,China) Abst ract :This pa per st udied how to m ine m eaning ful Web com m unities from forum .Cons truct ed user int era ct ion g raph ac-cording t o the hiera rchical st ructure a nd content of forumpost s.P roposed a nov el g raph clus tering a lg orit hm LOGC A t o exploit m eaning ful com m unities from la rge-scale net works.The experim enta l result s show t hat t his a pproach is effect iv e in dis cov ering Web com m unit ies from Internet forum . Key words:social net works;knowledge discovery ;dat a m ining ;Chinese forum 0 引言 近些年随着互联网的快速发展,论坛、博客等虚拟网络空间越来越受到网民们的欢迎。围绕这些虚拟网络空间,网络社区应运而生。网络社区是指由网民在电子网络空间进行频繁的社会互动形成的具有文化认同的共同体及其活动场所,也具有实在社区的基本要素:活动因素、人群(网民)、频繁的互动、共同的社会心理基础等。在网络社区中,网民迅速地交流沟通各种信息资讯,网络社区已经在人们的生活工作中发挥着越来越重要的作用。 研究虚拟网络社区的结构对于互联网研究中的一系列课题如确定社会热点、提供个性化服务具有重要意义。大量研究[1～3]表明,虚拟网络社区具有与现实社会网络类似的性质,如指数分布特性及尺度无关性等。通常虚拟网络社区可以用图的形式表示,其中网络中的节点表示个人,连线则表示人与人之间的某种联系。因此从虚拟网络中挖掘虚拟社区转换为从一个复杂图寻找聚类子图的问题。传统的图聚类方法是阶梯聚类,即首先给定一组节点集合及它们之间的相似度矩阵,将每个节点设为一个单独的类;然后将点间距离最近的点合并为一类,将它们与其他节点的距离加权平均后作为新类与其他节点的相似距离;最后继续重复类合并过程,直到所有的类都合并成为一类。但这种方法不能直接应用于网络社区挖掘问题,主要是因为在网络社区中有时难以定义用户之间的相似距离。 1 相关研究 图聚类问题在物理学、生物学、生态学和计算机科学中都有广泛的研究。较早提出的解决这一问题的方法是Ker-nigha n-Lin(K-L)算法[4]。该算法使用二分规则不断地将图进行二分,从而得到图聚类结果。对一般的图聚类结果,该方法的聚类结果较好,同时运行速度也较快;但该方法的缺点是需要预先确定所需分类类数,如果类数指定错误,则分类结果也可能出错。由于实际图聚类问题中往往无法预先指定所需分类数,该方法的实际应用有限。另外一种应用较广的图聚类方法是最大流最小分割(m a x flow-m in cut)法。F ord 等人[5]证明了对图进行最小分割的问题等同于求取图的最大流问题。在实际应用中,也存在大量算法性能优越的最大流最小分割算法,但该算法的主要缺点是不能对所分类的容量大小进行限制。Girva n 等人 [6] 近年提出了一种基于邻近度(betw eenness) 概念的图分类算法,该算法假定任一条边的邻近度为图中所有点间最短路径经过该边的次数,因为连接两个属于不同类节点的连线的邻近度显然大于连接两个属于同一类节点的邻近度,所以去掉这些邻近度较大的连线,就自然地得到了图聚类结果。该算法的思想非常直观,但缺点是计算图中所有点间的最短路径的计算量非常大,而且每去掉一条连线,就要重新计算一次,这使得该方法的计算非常复杂,不利于用于大型的图聚类问题。在互联网中寻找有效的用户社区的方法首先出现在Kleinberg 的HITS 算法中 [7] 。该算法使用限定特征值的方法 第26卷第8期2009年8月 计算机应用研究 Applicat ion Research of Com puters Vol.26No.8Aug.2009