最短路径问题网络分析毕业论文

1、        点：行动者、节点（actors, nodes）

即为社会网络中的一个功能个体（包括个人、单位、团体（看成一个整体）），在虚拟网络中表现为一个注册用户，ID等。

在社会网络研究领域，任何一个社会单位、社会实体或功能个体都可以看成是“节点”，或者行动者。

一个图中： 节点集合N={n1,n2,、、、n3}

2、        线,关系（relationship）：

用来刻画关系数据，关于接触、联络、关联、群体依附和聚会等方面的数据，这类数据把一个能动者与另外一个能动者联系在一起，因而不能还原为单个行动者本身的属性。如上图表示的线arc。

一般称由一条线连着的点是相互“邻接的（adjacent）”,邻接是对由两个点代表的两个行动者之间直接相关这个事实的图论表达。

一般有无向线、有向线、多值线、有向多值线。

由线构成的图无向图、有向图、有向多值、无向多值图。

3、        邻域（neighborhood）:

与某个特定点相邻的那些点成为该点的“邻域”。

4、        度数（degree）:

邻域中的总点数成为度数。（严格的说应该是“关联度”，（degree of connection））,一个点的度数就是对其“邻域”规模大小的一种数值侧度。

一个点（无向图）的度数，在邻接矩阵中，一个点的度数用该点所对应的行或者列的各项中的非0值总数来表示。如果是二值（有项）的，那么一个点的度数就是该点所在行和所在列的总合。

在有向图中，“度数”包括两个不同方面，表达社会关系的线的方向。分别称为“点入度（in-degree）”：直接指向该点的点数总合；和“点出度（out-degree）”：该点所直接指向的其它点的总数。因此，对应在有向图的矩阵上，点的入度：对应该点所在列的地总和上。出度：该点所在行的总和上。

所有点的度数总合：无向图的总度数查线（关系）即可，有项图的总度数查线的2倍。

5、        线路（walk）：

各个点可以通过一条线直接相连，也可以通过一系列线间接相连，在一个图中的这一系列线叫做一条“线路”。

6、        途经(path)：

线路中每个点和每条线都各不相同，则称该线路为“途经”，“途经”的“长度”，用构成该途经的线的条数来测量。

7、        距离(distance):

一个重要的概念，指连接两个点的最短路径（即捷径，geodesic）的长度。在图论中一般称作最短路经。要与“途经”的概念相区分。

8、        方向

主要是看有向图的方向问题。

9、        密度（density）

描述了一个图中各个点之间关联的紧密程度。一个“完备(complete)图”（在图论中称完全图）指的是一个所有点之间都相互邻接的图。这种完备性即使在小网络中也积极少见。密度这个概念试图对线的总分布进行汇总，以便测量图在多大程度上具有这种完备性。密度依赖于另外两个网络结构参数：图的内含度和图中各点的度数总和。密度指的是一个图的凝聚力的总体水平。

“密度”和“中心势”这两个概念代表的是一个图的总体“紧凑性（compactness）”的不同方面。

图的内含度（inclusiveness）：图中各类关联部分包含的总点数，也可表述为图的总点数减去孤立点的数。不同的图进行比较常用的侧度为： 关联点数/总点数 15/20=75%

各点度数总和：

密度计算公式： 图中实际拥有的连线数与最多可能拥有的线数之比，其表达式为2l/n(n-1)。  有向图的表达式为：l/n(n-1)

多值图的密度：需要估值多重度问题，显然多重度高的线对于网络密度的贡献要比多重度低的线的贡献大。比较有争议的一种测度。

巴恩斯（Barnes,1974）比较了两类社会网络分析：

10、        个体中心（ego-centric） 网研究

围绕特定的参考点而展开的社会网，密度分析关注的是围绕着某些特定行动者的关系的密度。计算个体中心网密度的时候，通常不考虑核心成员及与该成员有直接关系的接触者，而是只关注在这些接触者之间存在的各种联系（links）。

11、        社会中心（socio-centric）网研究

关注的是作为一个整体的网络关联模式，这是对社会网络分析的另外一类贡献，从这一角度出发，密度则不再是局部行动者的“个体网”密度，而是整个网络的密度。密度计算上文已经提到。

12、        点度中心度（point centrality）

一个图中各个点的相对中心度

13、        图的中心度（graph centrality） 即为中心势的概念

14、        整体中心度（global centrality）   （弗里曼Freeman 1979,1980）

整体中心度指的是该点在总体网络中的战略重要性。根据各个点之间的接近性（closeness）,根据不同点之间的距离。可以计算出图中某点与其他各个点之间的最短距离之和。

无向图：可以通过软件计算出来一个无向图中各个点之间的距离矩阵，那么一个点的“距离和”比较低的点与其他很多点都“接近”。接近性和距离和呈反向关系。

有向图：“内接近性（in-closeness）”和“外接近性(out-closeness)”来计算

15、        局部中心点

一个点在七紧邻的环境中与很多点有关联，如果一个点有许多直接相关的“邻点”，我们便说该点是局部中心点。

16、        整体中心点

如果一个点在网络的总体结构上占据战略上的重要地位，我们就说该点是整体中心点。

17、        局部中心度（local centrality）

局部某点对其邻点而言的相对重要性。测量仅仅根据与该点直接相连的点数，忽略间接相连的点数。在有向图中有内中心度（in-centrality）和外中心度（out-centrality）。也可以自定义距离为1或2进行测度，如果定义为4（大多数点的距离为4），就毫无意义，也没有信息。

18、        局部中心度的相对测度

点的实际度数与可能联络得最多度数之，注意要去掉该点本身。

19、        中心势（centralization） 弗里曼(freeman，1979)

指的不是点的相对重要性，而是整个图的总体凝聚力或整合度。很少有人试图界定一个图的结构中心思想。中心势描述的则是这种内聚性能够在多大程度上围绕某些特定点组织起来。因此，中心势和密度是两个重要的、彼此相互补充的量度。

核心点的中心度和其它点的中心度之差。因此得出概念：实际的差值总和和与最大可能的差值总和相比。

一般提法是：寻找网络中两点间的最短路径,即寻找连接这两点的边的总权数(可以是距离、时间、费用等)为最小的通路。图4为最短路径问题的一个例子。最短路径问题有两种算法。戴克斯特拉法1959年提出。其计算方法是：从始点vs,标以零值,并记在vs旁的方括号内。然后依节点序号顺序找出到达各点的最短距离,并说明来自何方,例如在节点v3处标上【v2,4】,即表示来自节点v2，距离累计为4。戴克斯特拉法可以通过编制计算程序,在计算机上运算。

Ⅰ考查目标 计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 Ⅱ考试形式和试卷结构 一、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构45分 计算机组成原理45分 操作系统35分 计算机网络25分 四、试卷题型结构 单项选择题80分（40小题，每小题2分） 综合应用题70分 Ⅲ考查范围 数据结构 【考查目标】 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 三、图 （一）图的概念 （二）图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用及其复杂度分析 1.最小（代价）生成树 2.最短路径 3.拓扑排序 4.关键路径 四、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找 （六）查找算法的分析及应用 五、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序 （三）气泡排序（bubblesort） （四）简单选择排序 （五）希尔排序（shellsort） （六）快速排序 （七）堆排序 （八）二路归并排序（mergesort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用 计算机组成原理