图的基本介绍

1.图的基本概念:简单来说图是一个由点和边构成的图形。
图可分为:有向图和无向图。

2.度的基本概念:链接节点的边的数量。
度可分为:出度(从节点指出的边)和入度(从节点指入的边),出入度只对于有向图来说。

3.连通图:对于一个无向图来说,任意一个节点i都能通过一些边到达节点i,此类图统称为连通图。
连通图又有:连通分量,最短路径。弱连通图和强连通图之分。

4.图直径:最远的两个节点之间的最近距离。

5.度中心性(degree):度(ndegree/(n-1))。

6.特征向量中心性(eigenvector):Ax=λx。

7.中介中心性(betweenness):经过该节点的最短路径/其余两两节点的最短路径。

8.连接中心性(closeness):n-1/节点到其余节点最短路径之和。

PageRank算法和HTS算法
1.PageRank算法
图的基本介绍
PageRank1=PageRank2/2
PageRank3=PageRank2/2+PageRank1
阻尼系数:
eg.阻尼系数为0.85,节点3有85%的可能性到达节点4,还有25%的可能性到达其他节点。

2.HTS算法
图的基本介绍
Hub:门户网站:eg.hao123;
Authority:百度、淘宝等。
Hub为节点的入;
Authority为节点的出。

1的Hub=3的Authority
3的Hub=4的Authority

上一篇:docker部署Jenkins


下一篇:hdu 4739 状压DP