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

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)

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

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