二部图社区划分算法的实现与验证
二部图社区划分算法的实现与验证
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
目录
1 引言 (1)
1.1 研究背景与意义 (1)
1.2 国内外研究现状 (1)
1.3 本文的主要工作和内容安排 (2)
1.3.1 主要研究内容 (2)
1.3.2 论文组织结构 (3)
2 相关理论概述 (5)
2.1 PR算法 (5)
2.1.1 PR算法基本概念 (5)
2.1.2 PR算法解析 (5)
2.2 随机游走.马尔可夫链 (7)
2.3 转移概率矩阵 (8)
2.4 六度分离理论 (8)
3 总体设计思路 (9)
3.1 随机游走模型 (9)
3.2 合并、划分原则 (11)
3.2.1 合并原则 (11)
3.2.2 划分原则 (11)
3.3 具体示例 (12)
4 详细设计 (16)
4.1 数据输入模块 (17)
4.2 能量转移模块 (17)
4.3 社区合并模块 (18)
4.4 社区划分模块 (20)
4.5 实验工具 (22)
4.5.1 Matlab (22)
4.5.2 Pajek (22)
5 实验结果分析 (23)
6 总结与展望 (28)
6.1 总结 (28)
6.2 展望 (28)
参考文献 (30)
致谢 (32)
1 引言
1.1研究背景与意义
随着Internet技术的快速发展，人类迈进了一个网络时代，从此人们的生活中将充满着各种复杂的网络。因此，人们需要深入的研究各种复杂网络，这样才能最大程度享受网络带来的便利。
二分网络是复杂网络的网络表现形式之一，二部图是描述二分网络的工具。二分网络是由两类节点和两类节点之间的连边构成的网络，同类节点间不存在连边，不同类节点间才存在连边。现实世界中存在许多这样的二分网络，如：演员和电影网、听众和歌曲网、科学家和论文网等。
有句俗语叫“物以类聚，人以群分”，比如听众歌曲网中喜欢同一种音乐类型、同一首歌或同一个歌手的人之间的联系是比较紧密的，反之联系就会较为疏远，这几类人分别形成了群体或者组，也称这为社区。随着人们对复杂网络的进一步研究，发现不同领域的复杂网络都具有社区结构，换句话说，若干个“群”或“组”可以构成整个网络。
在二分网络中研究社区划分是非常有价值的，如：演员电影网络中的社区是根据同一部电影的相关演员；听众歌曲网中的社区是根据同一首歌的相关听众；科学家论文网中的社区是根据同一篇论文的相关科学家等。对二分网络进行社区划分会给研究人员带来很大帮助，同时也打开了复杂网络研究的新视角。
1.2国内外研究现状
PR（PageRank）算法是Google搜索核心算法之一，是Google用来表示网页的等级和重要性的指标，该算法是利用随机游走理论的一个典型模型。
把二分网络以无权投影或加权投影的方式投影到单分网络上进行网络社区划分，是二分网络社区划分中常见的、传统的处理方式。但是用投影的方式，每次都只能对
单侧节点进行划分，而且投影会产生网络部分信息丢失等问题，从而影响实验结果。目前比较好的二分网络社区划分方式是直接在原始二分网络上进行社区划分，将网络中两类节点看作一类进行处理，这种方法保留了原始二分网络的大部分信息。因此以后进行二分网络社区划分的研究将把直接在原始二分网络上进行网络划分作为主要方向。
国内吴亚晶等人利用二分网络的聚类方法，提出了F 统计量判定最有聚类结果的方法，知道要划分的社团数目才能使用该方法。张鹏基于边集聚系数聚类方法设计出了二分社区发现算法，该算法是利用社区划分的终止条件——模块化函数。陈伯伦等人根据信号的稀疏分解算法即MP 算法对二分网络所对应的矩阵进行分解，从而进行社区划分。由于一些社区之间会出现节点重叠现象，杜楠提出了针对二分图重叠社区结构发现算法BeTector 。
国外Raghavan 等人提出了标签传播（LPA ）算法，该算法把网络用完全图表示，节点越相似标签传播越容易，该算法对于小型网络比较适用。Newman 等人在对单分网络进行社区划分时提出了模块度思想，Barber 等人把Newman 用于单分网络模块度的理论用于评价二分网络社区划分上，采用了（BRIM ）算法进行社区划分，该算法对于大型网络不适用；随后又在此基础上改进了BRIM 算法得到模块度凝聚（MAB ）算法，MAB 算法的复杂度比BRIM 算法高，但是使用该算法不需要事先知道社团个数。Palla 等人提出了k-团划分方法，该方法能够避免部分社区中的重叠节点对实验结果造成影响。Lehmann 等人根据Palla 等人提出的k-团划分方法得出了一种二分网络适用的社区划分方法——b a K ,-团划分方法，该方法也具有k-团划分方法的优点。
1.3 本文的主要工作和内容安排
1.3.1 主要研究内容
本文基于随机游走理论，提出了一种二部图单侧节点社区划分方法，将PR 算法应用于二分社交网络的社区划分中。其主要研究内容如下：
（1）二部图是描述二分网络的工具，用顶点表示具体网络中的节点，并用顶点间的连线表示网络节点之间的关系。首先将二部图中某一侧的每个顶点看成单独的一
个社区，把该侧顶点的能量初始化为1。
（2）利用二分网络节点间的连接关系，构造PR算法适用的转移概率矩阵，把两个不同维度的转移概率矩阵相乘，并根据小世界六度分离理论对其运算结果进行6次迭代，得到一个能量转移矩阵。
（3）利用矩阵中元素值大小作为选择社区合并点的原则，具体是先把能量转移矩阵对角线置零，随后把矩阵中最大元素值位置对应的两个社区合并为一个社区，根据行最大、列平均原则更新矩阵，依次类推，直到合并为一个社区为止。
（4）把二分网络中单侧节点进行无权、加权投影后，根据Q值计算公式，分别求出无权、加权投影后，每次社区合并后的Q值，在Q值最大处停止合并，就能得到二部图在单侧节点划分的最佳结果。实验结果表明，PR算法能对二分网络的单侧节点进行社区划分。
1.3.2论文组织结构
本论文的安排如下:
第一章：主要介绍了二部图社区划分算法的主要的技术及其发展，阐述了一些现阶段存在的二分网络的社区划分方法及其优缺点，就本文所研究的基于PR算法的二部图社区划分进行简单介绍。
第二章：主要对本文研究课题需要用到的相关理论进行概述，包括PR算法、随机游走.马尔可夫链、转移概率矩阵、六度分离理论。
第三章：提出了基于PR算法对二部图进行社区划分的总体设计思路，首先介绍了随机游走模型，继而介绍社区合并和划分原则，最后用一个简单的二分网络作为示例，用随机游走模型、社区合并及划分原则，对示例中的二分网络的单侧节点进行社区划分。
第四章：详细介绍了本文中实现二部图社区划分的程序，该程序分为四个模块：数据输入模块、能量转移模块、社区合并模块、社区划分模块。最后简单的介绍了MATLAB和Pajek等实验工具。
第五章：用南非妇女网络对本文中的二部图社区划分算法进行运行测试，根据二
分网络标准数据集，得到能量转移概率矩阵，经过6次迭代后对其进行社区合并、划分，根据计算出的无权、加权投影的Q值，得出南非妇女网络单侧节点划分结果。
第六章：根据以上几章的论述，对本文研究的二部图社区划分算法进行简单的总结，并对二部图社区划分算法进行展望。
2 相关理论概述
2.1PR算法
2.1.1PR算法基本概念
随着互联网时代的到来，网络上的信息越来越繁杂，想要获得有用的信息越来越难，所以现在就需要一种能将网络上繁杂的信息整理的有规律利于使用的搜索工具。如果有了这个搜索工具，那么在网络上找特定的信息就会像在有目录的书籍、有规律的图书馆找信息那样简单了。
Google是全球查询次数最多和信息量最大的搜索引擎,PR（PageRank）网页排序算法是Google使用最久的排序算法。PageRank是在20世纪90年代后期由在美国斯坦福大学就读博士的Larry Page 和Sergey Brin发明的算法。
PR算法的基础思想是：当某个链接存在在某个网页里，就说明该链接得到了该页面内容的认可，那么这个链接网页的内容的重要性会增大；换句话说，某一网页在被权威性较高的网页链接到和被权威性一般网页链接到相比，该网页在前者的情况下能得到的权威值更高。在PR算法中，把能表示网页权威性的值称为PR值，Google 是利用PR网页排序算法计算出每个网页的PR值，随后根据PR值的大小来决定网页排列顺序，PR值越高网页在搜索结果中排序就越靠前。要提高PR值有多种方法，如：让网页链接或反链接到PR值较高的网页、提高链接网页的数量及权威性、让该网页链接出现在知名度高流量大的网站中等。PR值与搜索内容无关，只与网络的链接结构有关。
2.1.2PR算法解析
PR（PageRank）算法具体表示为：把在某一个网页上的PR值除以在这个网页上的链接网页数，得到的值就是某一个网页分配给被链接网页的PR值，依次类推，将所有网页分配给该被链接网页的PR值相加，就计算出了该被链接网页的PR值。PR
算法觉得所有的网页的PR 值都被平均的分配到它所链接的网页，如此反复迭代，得到的网络上所有的网页PR 值都达到一种收敛、稳定的状态。如图2.1为PR 值的分配过程示意图：
图2.1 PR 值分配示意图
图中PR 值为100的网页链接到其他两个网页中，它就把自身的PR 值平均分配给它链接到的那两个网页，因此这两个被链接出来的网页分别得到的PR 值为50；以此类推，把被链接得到的PR 值与其自身的PR 值相加后继续链接到其他网页分配PR 值。如此反复迭代、一层一层的链接传递下去，最后全网络得到了一个相对稳定的PR 值。我们就可以根据相对稳定的PR 值的大小得出网页权威性的高低。所以PR 值可以用下面的公式计算：
()()()
()v N v PR c
u PR u
B v /∑∈= 公式中()u PR 表示网页u 的PR 值，v u 、分别表示两个网页，()u B 表示链接到网页u 的网页集合，()v N 表示网页v 里的所有链接数，c 表示规范化因子。
互联网的链接还可能存在一种现象：有部分网页是独立的，也就是说：有部分网页是彼此相连形成环状的，这部分网页没有对外部的网页形成链接，只有外部的网页对其进行链接。如图2.2所示，此类网络PR 值只进不出，与外部网络不能形成传递
关系，经过多次迭代PR值会变成0，这就是PR值的Rank Sink现象。
为了解决这一现象导致的问题，把上述公式改为：
()()()
()()d
v
N
v
PR
d
u
PR
u
B
v
-+
=∑
∈
1
/，其中d表示阻尼系数（一般取0.85）。利用这
一公式就可以解决Rank Sink现象。
2.2随机游走.马尔可夫链
随机游走(random walk)，又称为无规则行走，是指过去发生的与将来的发展是无关的，换句话说，在过去的种种表现的基础上，不能预测未来发展的方向与步骤。它的这种运动的每一步变化是无规则随机的，完全与前面所做的任何运动无关。随机游走的核心概念是任何无规则行走都遵守能量守恒定律，且这种能量守恒都有与之相对应的扩散运输定律。
随机游走模型目前在各个科研领域都有着十分重要的作用，其中在互联网领域与数据挖掘领域的应用较为宽泛。PR算法是随机游走理论的一个典型应用模型。随机游走模型的核心思想是：一些点在图上随机游走到任意顶点上，把一定的概率转移到图中的任意其它顶点。每一次随机游走都会转移一部分概率，用这些转移后形成的新的概率分布作为下一次随机游走的起始值，以此反复迭代这个过程，我们就可以得到一个基于稳定的概率分布。
在一种特定的环境下进行随机游走过程会形成一个马尔可夫链，随机游走也可以理解为马尔科夫链的一种特例，它的转移概率与这种特定的环境有关。
马尔可夫链，又称马氏链，在数学中表示为有马尔可夫性质的时间离散、状态离
散的转移过程。马尔可夫链想要预测下一步的发展状态，是要在知道当前的各种信息状态和当前一步的概率矩阵的基础上才能实现的。
我们把在n t =时刻在状态i 下的概率转移到1+=n t 时刻在状态j 的概率称为转移概率,记为：
[]()1,|1+===+n n P i x j x P ij n n
2.3 转移概率矩阵
马尔可夫提出了转移概率矩阵(transition matrix)。转移概率矩阵中的每个元素都是用概率表示的非负元素，它们能在特定的条件下相互转移。转移概率矩阵写为：
?
?
???
???????=mm m m m m P P P P P P P P P P 2
1
22221
11211
转移概率矩阵具有以下两种性质: 性质1：10≤≤ij P 性质2：()m i P m
j ij ,,2,11
1 ==∑=
2.4 六度分离理论
米尔格伦在1967年提出了六度分离理论(Six Degrees of Separation)。该理论指出在个人的关系网中，任何两个不认识的人都可以通过朋友、亲人认识，而且这两人之间最多只需要5个人。换句话说，你和世界上任何一个人之间的平均距离最多6个人，你最多需要通过5个人你就可以认识这世界上的任何一个陌生人，这是与国家、种族、肤色无关的。
3 总体设计思路
3.1 随机游走模型
二部图是用来描述二分网络的，具体为：二分网络中的节点可以用二部图中的顶点来表示，二分网络中节点间的关系体现在二部图中的顶点间的连边。
),,(E V U G =，G 表示一个二部图，U 、V 分别表示G 中的两类节点，E 为图G
中的边。集合U 或V 中内部的节点间是没有边相连的，连边只能出现在不同类节点间；集合E 中的任意边()
j i v u ,，必须满足V v U u j i ∈∈,。关系矩阵A 可以表示为：
??
??
?∈∈=else
V
j U i connect i if A ij 0,1
(1)
集合U 中和集合V 中的节点连接情况就分别用关系矩阵A 中的每行、每列来表
示。设集合U 中节点数为m ，集合V 中的节点数为n ，二部图G 的邻接矩阵A ~
可表述为：
??
?
???=????n n T m
n n m m m
A A A 00~ （2） 把集合U 中各个节点的能量初始化为1，把集合V 中各个节点的能量初始化为0。得
到集合U 的初始单位能量矩阵U
m m I ?：
??
??
?==else
j
i if I U
ij 01
（3）
集合U 的初始能量为1，此时可以把集合U 中的节点i u 拥有的自身和来自其他节
点的能量之和用向量i x 表示，把能量i x
按照公式4的规则进行能量转移得到转移概
率。
??
???='else
j connect i if x k R i
i
i 01 （4）
其中用i k 表示U 中节点i u 的度数，如果U 中的节点i u 与V 中的j v 之间有边相连，就说明节点i u 的能量可以转移到了节点j v 中，把节点j v 得到的所有能量相加，就可以得到集合U 中所有节点转移到集合V 中j v 节点的能量之和：∑='=m
i i i R R 1。
可以由i R '组合得到集合U 中节点把能量转移到集合V 中节点的转移概率矩阵n m R ?。
其中n m R ?每一行元素表示集合U 中的一个节点转移到集合V 中每一个节点的概率，每一列则表示集合V 中的一个节点得到来自于集合U 中每一个节点的转移概率。集合U 中节点对集合V 中节点的能量转移矩阵表示为：
n m U
m m n m R I S ????= （5）
用以上方法按照公式（5）把集合V 中每个节点的能量转移到集合U 中的每个节点。
??
???=else
j connect i if y k T j
j
j 01 （6）
其中j y 向量表示集合V 中的节点j v 得到的来自集合U 中每个节点的能量，j k 表示集
合V 中节点j v 的度数。根据j T 组合就可以得到一个集合V 中节点把能量转移到集合
U 中节点的转移概率矩阵m n T ?，由此可得，集合U 中每个节点将自身的能量转移到集
合U 中除自身以外的其他节点的能量矩阵可以表示为：
m n n m U
m m m m T R I S ??????=1 （7）
循环上述步骤进行n 次能量转移，得到能量转移矩阵n
m m S ?：
()
n
m
n n m U
m m n m m T R I S ??????= （8）
3.2 合并、划分原则
3.2.1 合并原则
当能量在网络中迭代n 次后得到转移概率矩阵n m m S ?，在矩阵n
m m S ?中的ij S 的大小
就表示i u 和j u 两个节点间联系的紧密程度。六度分离理论认为世界上任何的人和人之间的平均距离最多6个人，根据该理论得出能量在网络中经过六次迭代转移后得到的结果就能够满足评定原则，所以，能量转移次数n 取6。
本文采用的合并原则是：经过六次迭代后得到的能量转移矩阵6m m S ?，先把对角线上的元素置零，接着对矩阵中除对角线外元素进行遍历，依次找到矩阵6
m m S ?中每行和
每列的元素最大值的位置（i ，j ），把最大值的位置对应的两个社区（i ，j 社区）合
并。当社区合并之后，对矩阵6m m S ?中对应的i 行、j 行和i 列、j 列进行合并，更新矩
阵是根据求行最大、列平均的方法，具体是把第i 行和j 行中的元素一一对应求出最大值，写到第i 行上，删除第j 行元素；把第i 列和j 列中的元素一一对应求出平均值，写到第i 列上，删除第j 列元素。以此类推，直到所有社区都合并成一个社区，此时得到合并的结果为一棵树状图。
3.2.2 划分原则
二部图中评价社区划分结果的好坏有很多中方法，如聚集系数、模块度等。本文对二分网络的单侧节点进行社区划分，借鉴了二分网络的无权投影和加权投影到单分网络上的社区划分评价标准，采用模块度Q 值大小来评价网络中社区划分的好坏。模块度Q 值的大小，主要取决于网络中社区内部的边数和社区之间的边数，社区内部边数较多并且社区之间的边数较少的社区划分结果是比较好的。模块度定义为：
()
∑-=-=i
i ii e Tre a e Q 22 （9）
其中ii e 表示社区内部边在所有边中所占的比例，∑=i
ij i e a ，它表示与第i 个社区相连
的边在所有边中的比例，x 表示矩阵x 中所有元素的和,∑=i
ij e Tre 表示矩阵中对角
线上的各元素的和。
3.3 具体示例
图3.1 二部图
我们把上图3.1所示的二分网络作为本文研究二部图单侧节点社区划分的例子。首先把上侧节点能量初始为1，根据本章3.1节的1—6个公式得到该二分网络的两个转移概率矩阵56?R 和65?T ，以及单位能量矩阵66?I ，其中56?R 和65?T 为：
???
???
???
???????????=?212100021210003111000013110002121000
21215
6R ???????
?????????=?131310001313100000212100
000313110003131165T 根据公式：6556661
66??????=T R I S ，得到经过一次能量转移后的矩阵：
表3.1 一次能量转移矩阵
A
B
C
D
E
F
b
a
c e
d
根据()6
6556666
66??????=T R I S 进行能量的6次转移，得到一个矩阵，这个矩阵就是
二分网络单侧节点间的能量转移矩阵。根据下表3.2的六次迭代后的转移概率矩阵，我们可以得到单侧节点能量转移的情况。表中的行表示一个节点的能量转移到其他同类节点的能量，列表示得到的其他的同类节点转移的能量，对角线上的值表示在经过6次能量转移后本身的能量的剩余量。例如节点A 把0.1218能量转移到了节点D 上，节点A 得到了节点D 转移的0.0812能量，节点A 经过6次能量转移剩余能量为0.2354。6次能量转移后的矩阵为：
表3.1 六次能量转移矩阵
把表3.2中元素对角线置零后，找出表中最大的元素0.3067，得出A 社区与C 社区联系比较紧密，所以把社区A 和C 两个社区合并为AC 一个社区。随后把表3.2中的矩阵进行合并，把A 行和C 行中相对应的元素最大的放在A 行，C 行元素删除；求出A 列和C 列中对应元素的平均值放在A 列，把C 列元素删除。矩阵合并结果如表3.3所示：
表3.2 AC 合并后的矩阵
以次类推，在新的矩阵中重复上述方法，直到整个二分网络单侧节点合并成一个社区为止，得到合并的结果为一棵树状图，如下图3.2所示。
图3.2 上侧节点合并过程
分别把该二分网络的上侧节点进行无权投影和加权投影，经过无权投影后得到的社区合并过程Q 值变化如图3.3所示：
图3.3 无权投影后社区合并过程Q 值变化
经过加权投影后得到的社区合并过程Q 值变化如图3.4所示：
图3.4 加权投影后社区合并过程Q 值变化
C E F
B D
根据图3.3、3.4所示，Q值在第4次合并完成后达到最大值，所以在第4次合并结束后停止合并。联系图3.2所示内容，划分为两个社区为最佳划分结果。该二分网络上侧节点社区划分结果图如图3.5所示，其中1~6分别表示A~F。
图3.5上侧节点划分结果
根据图3.3、3.4所示，虽然划分结果相同，但是Q值大小不同，经过无权投影后最大Q值为0.3517，而加权投影后最大Q值增大为0.4231。把模块度Q值作为评价社区划分好坏的标准，在0.3~0.7之间表明有明显社区，Q值越大社区划分结果越好。所以对于二部图单侧节点投影进行社区划分，加权投影优于无权投影。
图的算法实现课程设计
数据结构与算法 课程设计报告 课程设计题目：图的算法实现专业班级：信息与计算科学1001班姓名：学号： 设计室号：理学院机房 设计时间： 2011-12-26 批阅时间：指导教师：成绩：
图的算法实现 目录 一．设计内容 二．功能设计流程 三．详细设计 四．调试 五．总结 六．参考文献 七．附录源代码
一、设计内容： 1.实验内容 图的算法实现 （1）将图的信息建立文件； （2）从文件读入图的信息，建立邻接矩阵和邻接表； （3）实现Prim、Kruskal、Dijkstra序算法。 2.实现的任务：从文件中读入图的信息，建立图的邻接矩阵和邻接表，实现Prim、Kruskal、Dijkstra 3.本系统涉及的知识点 Prim、Kruskal、Dijkstra、邻接矩阵和邻接表存储。 4.功能要求 1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 2．对系统进行功能模块分析、画出总流程图和各模块流程图。 3．用户接口要求使用方便、简洁明了、美观大方、格式统一。 4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。 5．所有程序需调试通过。 二、功能设计流程： 图的算法 实现 邻接矩阵邻接表 Prim算法Kruskal算法Dijkstra算法
开始 辅助数组初始 输出生成树的边并计算其权值 新顶点并入U 集后重新选择最小边：遍历点，若g.edges[k][j]!=0 && g.edges[k][j] 网络社区划分算法 目录 ? 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条边的一个加权无向网络，反应的是在一天之用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。 本文主要介绍基于Retinex理论的雾霭天气图像增强及其实现。并通过编写两个程序来实现图像的去雾功能。 1 Rentinex理论 Retinex（视网膜“Retina”和大脑皮层“Cortex”的缩写）理论是一种建立在科学实验和科学分析基础上的基于人类视觉系统（Human Visual System）的图像增强理论。该算法的基本原理模型最早是由Edwin Land（埃德温?兰德）于1971年提出的一种被称为的色彩的理论，并在颜色恒常性的基础上提出的一种图像增强方法。Retinex 理论的基本内容是物体的颜色是由物体对长波（红）、中波（绿）和短波（蓝）光线的反射能力决定的，而不是由反射光强度的绝对值决定的；物体的色彩不受光照非均性的影响，具有一致性，即Retinex理论是以色感一致性（颜色恒常性）为基础的。 根据Edwin Land提出的理论，一幅给定的图像S(x,y)分解成两幅不同的图像：反射物体图像R(x,y)和入射光图像L(x,y)，其原理示意图如图8.3-1所示。 图-1 Retinex理论示意图 对于观察图像S中的每个点(x,y)，用公式可以表示为： S(x,y)=R(x,y)×L(x,y) （1.3.1）实际上，Retinex理论就是通过图像S来得到物体的反射性质R，也就是去除了入射光L的性质从而得到物体原本该有的样子。 2 基于Retinex理论的图像增强的基本步骤 步骤一: 利用取对数的方法将照射光分量和反射光分量分离，即： S＇(x, y)=r(x, y)+l(x, y)=log(R(x, y))+log(L(x, y))； 步骤二：用高斯模板对原图像做卷积，即相当于对原图像做低通滤波，得到低通滤波后的图像D(x,y)，F（x, y）表示高斯滤波函数： D(x, y)=S(x, y) *F（x, y）； 步骤三：在对数域中，用原图像减去低通滤波后的图像，得到高频增强的图像G （x, y）： G(x,y)=S＇(x, y)-log(D(x, y)) ； —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/f810711013.html, 哈密顿图判定问题的多项式时间算法 姜新文等** （４１００７３，国防科技大学计算机学院，长沙） Abstract: 本文给出一个称为 问题的定义及其多项式时间判定算法。已经证明包括哈密顿图判定问题在内的众多 完全问题可以多项式归结到 问题。 问题的多项式时间判定算法就是 完全问题的多项式判定算法。本文结果暗示 。本文涉及的内容属于简单的图论问题算法设计的入门性范畴，被计算机、数学和信息安全等类专业本科以上知识背景覆盖。相关专业本科甚至专科以上学生通过适当求教算法设计、计算复杂性、图论、运筹学和密码算法相关教师和权威可以阅读本文。 Key words: Algorithm, problem, problem, complete problem 1 问题引入及若干定义 哈密顿图判定问题是 完全问题。为了求解该问题，我们需要对问题进行转化。为缩短证明长度，以分段确认，分割围歼，综合众多意见，我们提出 问题，并将注意力集中在 问题多项式时间判定上。 算法是一堆动作的有序集合。为一个问题设计算法是容易的，将一些动作凑在一起即可。设计算法的困难性和严肃性在于，你的算法是否实现了你的计算目标？于是需要证明。而如何证明常常让人无从着手。 问题是一个人工构造的问题，它的特别的结构特性，使我们容易找到时间复杂性为关于问题规模的多项式函数算法并证明其正确性。该问题的定义已经可以在很多文章中查到。为了本文的完整性，我们首先转述对 问题的定义。 定义1称 , , , , 是加标多级图(labeled multistage graph)，如果满足以下条件： 1. 为顶点集合， ∪ ∪ ∪?∪ ， ∩ ?，0 , ， 。如果 ∈ ，0 ，称 所在级为 级，也称 是 级的顶点。 称为 的级。 2. 为边的集合， 中的边均为有向边，它用三元组? , , ?表示。如果? , , ?∈ ，1 ，则 ∈ ， ∈ 。称? , , ?为 的第l级的边。 3. 和 都只包含唯一顶点。称 中的唯一顶点为源点，记为 ，称 中的唯一顶点为汇点，记为 。 4. 对每个顶点 ∈ ，都有一个边集 ( )作为标记， ( )? 。称 ( )为 的边集。 例如，图1所示的两个图，都是加标多级图。各个顶点的边集的一组可能的取值定义如下。对左边的图， (1) ， (2) ， (3) , , , ， (4) , , ， (5) , , ， (6) , , , ， (7) ， (8) , , , ， ( ) , , , , 。对右边的图, (1) ?， (2) ?， (3) ?， (4) , , ， (5) , , ， (6) , , ， (7) (7 ) , , , ， (8) , , , ， ( ) ?。 定义2设 , , , , 是一个加标多级图， ? ? (1 ， )是 中一**Please visit https://www.docsj.com/doc/f810711013.html,/u/1423845304 for revision information 网络社区划分方法及评价 【摘要】网络社区结构是社会网络最普遍和最重要的拓扑属性之一，其特点是，同一社区内的节点连接密集，不同社区间的节点连接稀疏。揭示网络社区结构对分析复杂网络拓扑结构、理解其功能、发现其隐含模式、预测其行为都具有十分重要的理论意义，在社会网、生物网和万维网中具有广泛应用。本文主要从网络社区划分的起源、常见的社区划分方法及社区评价准则等三个方面介绍网络社区划分研究的相关工作。 【关键词】复杂网络；网络社区；社区划分；社会网络分析；社区的评价；局部社区划分 0.引言 网络科学将系统内部的各个元素作为节点，元素之间的关系视为连接，那么系统就构成了一个具有复杂连接关系的网络。然而，近几年的实证研究表明，这些看似毫不相干的且形态各异的真实系统的拓扑抽象都具有某些共同的拓扑性质，如小世界与无标度特性等等。由于它们所表现出来的拓扑性质与随机网络、规则网络等有着天壤之别，且节点众多，因此被称为复杂网络。目前，复杂网络成为技术、生物乃至社会各类复杂系统的非常一般的抽象方法与描述骨架，相关研究成为重要的学科交叉研究前沿。 所谓社区(community)即指网络的内聚子图，其基本特征表现为子图内部链接丰富，不同子图之间连接相对稀少。 1.常见网络社区划分方法 1.1基于优化思想的算法 基于优化思想的算法将复杂网络社区划分转化为优化问题，通过最优化预定义的目标函数来计算复杂网络的社区结构。比如K-L算法、谱平分法、随机游走(Random Walks)算法和派系过滤(CMP)算法等。这些算法的突出优点是速度比较快，效率显著。但是缺点也很突出，这一类算法都需要知道网络社区的数目，甚至KL算法还需要知道每个社区中各有多少节点，才能正确划分。这显然不适于网络未知社区的探索。 1.2社会网络分析方法 源于社会网络分析中寻找社区结构的传统算法，主要基于分级聚类思想，按照各个节点之间连接的相似性或者强度，把网络自然地划分为各个子群。其具体实现方式又有两种：其一是往网络中添加边，即凝聚方法(agglomerative method)；其二是又从网络中移除边，即分裂方法(divisive method)。凝聚方法的基本思想是基于网络中节点某种相似性分层进行聚类的。初始时，每个节点为一个社区，然 图像拼接算法及实现（一） 来源：中国论文下载中心 [ 09-06-03 16:36:00 ] 作者：陈挺编辑：studa090420 论文关键词：图像拼接图像配准图像融合全景图 论文摘要：图像拼接(image mosaic)技术是将一组相互间重叠部分的图像序列进行空间匹配对准,经重采样合成后形成一幅包含各图像序列信息的宽视角场景的、完整的、高清晰的新图像的技术。图像拼接在摄影测量学、计算机视觉、遥感图像处理、医学图像分析、计算机图形学等领域有着广泛的应用价值。一般来说,图像拼接的过程由图像获取,图像配准,图像合成三步骤组成,其中图像配准是整个图像拼接的基础。本文研究了两种图像配准算法:基于特征和基于变换域的图像配准算法。在基于特征的配准算法的基础上,提出一种稳健的基于特征点的配准算法。首先改进Harris角点检测算法,有效提高所提取特征点的速度和精度。然后利用相似测度NCC(normalized cross correlation——归一化互相关),通过用双向最大相关系数匹配的方法提取出初始特征点对,用随机采样法RANSAC(Random Sample Consensus)剔除伪特征点对,实现特征点对的精确匹配。最后用正确的特征点匹配对实现图像的配准。本文提出的算法适应性较强,在重复性纹理、旋转角度比较大等较难自动匹配场合下仍可以准确实现图像配准。 Abstract：Image mosaic is a technology that carries on the spatial matching to a series of image which are overlapped with each other, and finally builds a seamless and high quality image which has high resolution and big eyeshot. Image mosaic has widely applications in the fields of photogrammetry, computer vision, remote sensing image processing, medical image analysis, computer graphic and so on. 。In general, the process of image mosaic by the image acquisition, image registration, image synthesis of three steps, one of image registration are the basis of the entire image mosaic. In this paper, two image registration algorithm: Based on the characteristics and transform domain-based image registration algorithm. In feature-based registration algorithm based on a robust feature-based registration algorithm points. First of all, to improve the Harris corner detection algorithm, effectively improve the extraction of feature points of the speed and accuracy. And the use of a similar measure of NCC (normalized cross correlation - Normalized cross-correlation), through the largest correlation coefficient with two-way matching to extract the feature points out the initial right, using random sampling method RANSAC (Random Sample Consensus) excluding pseudo-feature points right, feature points on the implementation of the exact match. Finally with the correct feature point matching for image registration implementation. In this paper, the algorithm adapted, in the repetitive texture, such as relatively large rotation more difficult to automatically match occasions can still achieve an accurate image registration. Key words: image mosaic, image registration, image fusion, panorama 第一章绪论 数据结构课程设计报告 设计题目：图的算法实现 班级： 学号： 姓名： 数据结构课程设计报告内容 一．课程设计题目 图的算法实现 【基本要求】 （1）建立一文件，将图的信息存在此文件中； （2）从此文件读入图的信息，建立邻接矩阵和邻接表； （3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。 二．算法设计思想 （1）图的存储结构： 邻接矩阵：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。 邻接表：对图中的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成，其中邻接点域指示与顶点Vi邻接的点在图中的位置，链域指示下一条边或弧的结点；数据域存储和边或弧相关的信息。每个链表上附设一个表头结点。在表头结点中，除了设有链域指向链表中第一个结点之外，还设有存储顶点Vi的名或其他相关信息的数据域。 （2）prim算法 是一种求图的最小生成树的算法。 假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。此时，TE中必有n-1条边，T=(V，TE)为G 的最小生成树。Prim算法的核心:始终保持TE中的边集构成一棵生成树。 （3）Kruskal算法 Kruskal算法是另一种求最小生成树的算法 他的基本思想是以边为主导地位，始终选择当前可用（所选的边不 能构成回路）的最小权植边。所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。 具体实现过程如下： <1> 设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T={V,空}，图中每个顶点自成一格连通分量。 <2> 在Ｅ中选择一条具有最小权植的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到Ｔ中；否则，即这条边的两个顶点落到同一连通分量上，则将此边舍去（此后永不选用这条边），重新选择一条权植最小的边。 <3> 如此重复下去，直到所有顶点在同一连通分量上为止。 (4)Dijkstar算法 Dijkstra算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展直到扩展到终点为止。 基本思想 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s 开始计算)。 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。…重复该操作，直到遍历完所有顶点。 操作步骤 <1>初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长 3. 要求对于邻接矩阵和邻接链表给出从G 到T G 的算法，并计算其复杂度。 对于邻接矩阵问题十分简单，直接求矩阵的转置即可，意味着把行换成列，把列换成行，对每行操作为O(|V|)，需要对|V|行操作，时间复杂度为O （|V|^2）。 对于邻接链表，很明显要遍历链表的所有结点来看：如果对于u 结点其指向的结点中有v,则在新的链表中，创建一条从v 的链表指向u 的路径，因此需要遍历所有的链表元素，因此时间复杂度为O （|V|+|E|）。 3. 给出一个多图（多图为包含重复边和自循环边的图）去除冗余边的复杂度为O(V+E)的算法。 遍历邻接链表的所有结点，对于结点u ，如果其链表中还有u ，则去除所有的u ；如果还有重复的v ，则去除除了第一个v 以外的v 结点（这里的标记方法有很多种，可以用个数组）。这样的复杂度应该在O(V+E)。 4. 求解平方图的问题 算法如下：遍历G 的邻接矩阵，对于结点u ，如果存在u 到v 的路径，则在G^2的邻接矩阵u 中加入v,然后再遍历v 结点的链表，如果存在v 到w ，则将w 也加入到G^2的邻接矩阵u 中。 时间复杂度：这样，再遍历u 的时候，如果遍历到了u →v 这条边，那就在看v 的链表，而v 的链表里最多有|V|个结点，因此总的复杂度为O （|V|+|V|·|E|）。 6. 邻接矩阵求通用汇点（入度为|V|-1但是出度为0）的算法 算法如下：从（1，1）开始扫描邻接矩阵，如果（i,j ）是0，则下一个扫描（i,j+1）;如果（i ，j ）是1，则下一个扫描（i+1，j ）,当i 或者j 任一方到达|V|时停止。 这样，在最坏的情况下，扫描一行加一列或者一列加一行的结点，一共有2*|V|-1时间复杂度，因此为O(V)。 7. 关联矩阵，说明BB^T 每个元素是什么意思。 其中bij = -1 （如果边j 从结点i 发出） 1（如果边j 进入i 结点） 0（其他） 此处需要分类讨论：要明白B^T 中i 行相当于B 中第i 列。 ①BB^T 对角线上的元素，T B B （i ，i ） = ∑=| E |1 j 2 bij ，这样如果存在一条由i 发出或者进 入i 的边，都会在T B B （i ，i ）中加一（因为就算是-1平方之后也是1），因此T B B （i ，i ）就是代表由多少条边从i 发出或者进入。 ②BB^T 非对角线元素，T B B （i ，j ） = ∑=| |1 k E jk ik b b ,由公式或者读者自己画矩阵图可以 得出，如果k 边从i 发出从j 进入，或者反过来，bik*bjk 就等于-1，否则就为0。原因是i,j 我国基本比例尺地形图分幅与编号的计算方法 韩丽蓉 (青海大学水电系,青海西宁 810016) 摘要:通过实例探讨了我国基本比例尺地形图分幅与编号的计算方法,此方法可以帮助使用者快速地由某点的经纬度值计算出高斯投影带带号和某比例尺地形图的图幅编号,在测绘工作中具有一定的实用性。 关键词:分幅;编号;六度带;中央子午线经度 中图分类号:K 99 文献标识码:B 文章编号:1006-8996(2006)06-0079-04 1 高斯分带投影 1.1 基本概念 在地理坐标中,经度是以经过英国格林威治天文台的子午面作为起算点(零度),自西向东逆时针至180°为东经,自东向西顺时针从0°至180°为西经,东、西经180°经线是重合的。地图投影是把不可展的 地球椭球体面上的经纬网,按照一定的数学法则转绘到平面上[1,2]。我国的8种国家基本比例尺地形图 (1:1000000～1:5000)中,除了1:1000000万地形图采用国际通用的正轴等角割圆锥投影外,其余7种国家基本比例尺地形图统一采用高斯投影。 高斯投影中限制长度变形的最有效方法是按一定经差将地球椭球面划分成若干投影带,通常投影分为六度带和三度带。分带时既要控制长度变形使其不大于测图误差,又要使带数不致过多以减少换带计算工作。我国1:500000～1:25000的比例尺地形图多采用六度带高斯投影,1:10000～1:5000的地形图采用三度带高斯投影。我国基本比例尺地形图的分幅与编号需要用到某地所在的1:1000000 地形图(经差6° )的中央子午线经度,故需计算该六度带的带号及中央子午线经度。1.2 投影带带号和中央子午线经度的计算方法 1.2.1 六度带 从格林威治零度经线起,每隔经差6°分为一个投影带,自西向东逆时针分带,全球依次编号为1,2, 3,……60,每带中间的子午线称为中央子午线[1,2]。 东半球从经度0°逆时针回算到东、西经180°,投影带号为1～30。假如知道东半球某地区的平均大地经度L 东,则其投影带带号M 东和中央子午线经度L 6东的计算公式为: M 东=[L 东Π6](取整数商)+1(有余数时);L 6东=(6M 东-3)° (东经)西半球投影带从东、西经180°逆时针回算到0°,投影带号为31～60,假如知道西半球某地区的平均大地经度L 西,则其投影带带号M 西和中央子午线经度L 6西的计算公式为: M 西=[(360°-L 西)Π6](取整数商)+1(有余数时)=[(180°-L 西)Π6](取整数商)+1(有余数时)+30;L 6西={360°-(6M 西-3)°}(西经) 1.2.2 三度带 自东经115°子午线起,每隔经差3°自西向东分带,依次编号为1,2,3,……120[1,2] 。 东半球有60个投影带,编号为1～60,假如知道东半球某地区的平均大地经度L 东,其投影带带号N 东和中央子午线经度L 3东的计算公式为: 收稿日期:2006-07-10 作者简介:韩丽蓉(1967—),女,撒拉族,青海循化人,副教授,硕士。第24卷 第6期2006年12月 青海大学学报(自然科学版)Journal of Qinghai University (Nature Science ) Vol 124No 16Dec 12006 数据结构课程设计报告 图的最短路径算法的实现 班级：计算机112班 姓名：李志龙 指导教师：郑剑 成绩：_______________ 信息工程学院 2013 年1 月11 日 目录 一、题目描述 -------------------------------------------------------------------- 1 1.1题目内容-------------------------------------------------------------------- 1 2.2题目要求-------------------------------------------------------------------- 1 二、设计概要 -------------------------------------------------------------------- 2 2.1程序的主要功能----------------------------------------------------------- 2 2.2数据结构-------------------------------------------------------------------- 2 2.3算法分析-------------------------------------------------------------------- 2 三、设计图示 -------------------------------------------------------------------- 4 四、详细设计 -------------------------------------------------------------------- 5 五、调试分析 -------------------------------------------------------------------- 8 六、运行结果 -------------------------------------------------------------------- 9 七、心得体会 ------------------------------------------------------------------- 11参考资料 ------------------------------------------------------------------------ 12 一、图的邻接矩阵存储 1.存储表示 #define vexnum 10 typedef struct{ vextype vexs[vexnum]; int arcs[vexnum][vexnum]; }mgraph; 2.建立无向图的邻接矩阵算法 void creat(mgraph *g, int e){ for(i=0;i for(i=0;i 基本数字图像处理算法的matlab实现 1.数字图像处理的简单介绍 所谓数字图像就是把传统图像的画面分割成为像素的小的离散点，各像素的灰度值也是用离散值来表示的。 数字图像处理是通过计算机对图像进行去除噪声、增强、复原、分割、提取特征等处理的方法和技术。 2.图像的显示与运算 2.1图像的显示 Matlab显示语句 imshow（I,[lowhigh]）%图像正常显示 I为要显示的图像矩阵。,[lowhigh]为指定显示灰度图像的灰度范围。高于high的像素被显示成白色；低于low的像素被显示成黑色；介于high和low之间的像素被按比例拉伸后显示为各种等级的灰色。 subplot(m,n,p) 打开一个有m行n列图像位置的窗口，并将焦点位于第p个位置上。 2.2图像的运算 灰度化将彩色图像转化成为灰度图像的过程成为图像的灰度化处理。彩色图像中的每个像素的颜色有R、G、B三个分量决定，而每个分量有255中值可取，这样一个像素点可以有1600多万（255*255*255）的颜色的变化范围。而灰度图像是R、G、B三个分量相同的一种特殊的彩色图像，其一个像素点的变化范围为255种，所以在数字图像处理种一般先将各种格式的图像转变成灰度图像以使后续的图像的计算量变得少一些。灰度图像的描述与彩色图像一样仍然反映了整幅图像的整体和局部的色度和亮度等级的分布和特征。图像的灰度化处理可用两种方法来实现。 第一种方法使求出每个像素点的R、G、B三个分量的平均值，然后将这个平均值赋予给这个像素的三个分量。 第二种方法是根据YUV的颜色空间中，Y的分量的物理意义是点的亮度，由该值反映亮度等级，根据RGB和YUV颜色空间的变化关系可建立亮度Y与R、G、B三个颜色分量的对应：Y=0.3R+0.59G+0.11B，以这个亮度值表达图像的灰度值。 灰度是灰度级的函数，它表示图象中具有每种灰度级的象素的个数，反映图象中每种灰度出现的频率。 图像增强的目标是改进图片的质量，例如增加对比度，去掉模糊和噪声，修正几何畸变等；图像复原是在假定已知模糊或噪声的模型时，试图估计原图像的一种技术。 Matlab图像格式转换语句 rgb2gray(I) %从RGB图创建灰度图 imhist(I) %画灰度直方图 图像的线性变换 D B=f(D A)=f A*D A+f B Matlab源代码： I1=imread('F:\图片2.jpg'); subplot(2,2,1);imshow(I1);title('原图'); I2=rgb2gray(I1); %灰度化图像 subplot(2,2,2);imshow(I2);title('灰度化后图'); [M,N]=size(I2); subplot(2,2,3) [counts,x]=imhist(I2,60); %画灰度直方图 counts=counts/M/N; stem(x,counts);title('灰度直方图'); g=zeros(M,N);%图像增强 网络社区划分算法 目录 ?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条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。网络社区划分算法
基于matlab的图像去雾算法详细讲解与实现-附matlab实现源代码
大型复杂网络中的社区结构发现算法
哈密顿图判定问题的多项式时间算法
网络社区划分方法及评价
图像拼接算法及实现.doc
图的算法实现
基本的图算法
新旧图幅编号
图的最短路径算法的实现
图的两种存储结构及基本算法
基本数字(精选)图像处理算法的matlab实现
网络社区划分算法