来源：知乎------图解：什么是“图”？ - 知乎
图论的起源是基于一个现实生活中的事例：
河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？
欧拉在1735年提出，并没有方法能圆满解决这个问题，他更在第二年发表在论文《柯尼斯堡的七桥》中，证明符合条件的走法并不存在。
欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数，这样的点称为偶顶点。相对的，连有奇数条线的点称为奇顶点。由于柯尼斯堡七桥问题中存在4个奇顶点，它无法实现符合题意的遍历（一笔画问题：一笔画图形的必要条件是：奇点数目是0或者2）。
之后，不少数学家都尝试去解析这类事例。而这些解析，最后发展成为了数学中的图论。
图的定义：图是由一组顶点和一组能够将两个顶点相连的边组成的
图是一种非线性表数据结构，图中的元素我们叫做顶点，图中建立的连接关系我们叫做边。图主要分为四种：无向图、有向图、加权图、加权有向图。
我们把边没有方向的图叫做“无向图”，把有边有方向的图叫做“有向图”，把边带有权重的图叫做“加权图”。
（1）无向图和有向图
（2）加权图和加权有向图
在图的表示中，我们定义度的概念。对于无向图而言，一个顶点的度是指跟该顶点相连接的边的条数；无向图的度为与顶点连接的边的条数；对于有向图而言，我们分别定义入度和出度，顶点的入度表示有多少条边指向这个节点，顶点的出度表示有多少条边以这个节点为起点指向其他节点。
图的存储方法主要有两种：邻接表（Adjacency List）和邻接矩阵（Adjacency Matrix）。
（1）邻接矩阵
邻接矩阵，顾名思义，就是利用矩阵去描述图，它的底层依赖于一个二维数组。对于无向图而言，如果与之间有边，那么我们就把和标记为1，它们之间没有边就标记为0；对于有向图而言，如果 到 之间，有一条箭头从 指向 的边，那我们就将 标记为 1。同理，如果有一条箭头从 指向 的边，我们就将 标记为 1。对于带权图，数组中就存储相应的权重。
我们使用邻接矩阵来表示图，虽然的确很直观明了，但是却比较浪费空间。
其一，对于无向图来说，永远等于，我们只需要使用一半矩阵就可以成功地表示，那另一半空间就被浪费掉了；
其二、如果我们存储的是稀疏图，也就是顶点很多，但每个顶点的边并不很多，此时邻接矩阵的存储方法就更加浪费空间了。好比微信有好几亿的用户，对应到图上就是好几亿的顶点。但是每个用户的好友并不会很多，一般也就几百个而已。如果我们用邻接矩阵来存储，那绝大部分的存储空间都被浪费了。
总结一下，当图为稀疏图、顶点较多，即图结构比较大时，更适宜选择邻接表作为存储结构。当图为稠密图、顶点较少时，使用邻接矩阵作为存储结构较为合适。
（2）邻接表
我们使用一个以顶点为索引的列表数组，其中数组中的每个元素都指向一个单独的链表，该链表存储了与数组中顶点相邻的所有顶点。
相比于邻接矩阵，邻接表比较节省存储空间，但是使用起来却比较耗费时间。不过，它的形式更为自由和灵活，比如，在链表过长的情况下，我们可以把链表用平衡二叉查找树（红黑树）替代，这样的话就比较高效了。
（1）子图
子图是图论的基本概念之一，指节点集和边集分别是某一图的节点集的子集和边集的子集的图。
若这个节点子集或边子集是真子集，则称这个子图为真子图；
若图G的每一个节点也是它的子图H的节点，则称H是G的支撑子图。
设S是V(G)的子集，以S为节点集，以G的所有那些两端点都在S内的边组成边集，所得到的G的子图称为S在G中的导出子图，或更确切地，节点导出子图。
设B是E(G)的子集，由G的所有与B内至少有一条边关联的节点组成节点集，以B为边集，所得到的G的子图称为B在G中的边导出子图；
对于某种性质P，若一个图的具有P的子图不是任何具有P的子图的真子图，则称它为具有P的极大子图，在所有极大子图中，边数最多的那个称为最大子图。
（2）连通图和连通分量
1．顶点间的连通性
在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。
2．连通图
若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图(Con-nected Graph)。
3．连通分量
无向图G的极大连通子图称为G的最强连通分量(Connected Component)。
4. 有向图的连通性
参考：https://blog.csdn.net/Mmyine/article/details/105066677
有向图中只有极大强连通图的概念没有极小连通图。
注：有向图的概念和无向图的类似不再赘述。
综上：
1. 强连通图的极大强连通子图是其本身。
2. 非强连通有多个极大强连通子图，就是强连通分量
来源：谁是社会网络中最重要的人？ - 知乎
人与人之间的相互联系构成了我们这里将要讨论的社会网络。网络由节点（node）和连接它们的边（edge）构成。例如，你的微信好友可以看作是网络中的一个节点，而连接节点的边可以看作是朋友关系。在万维网中，每个网页是一个节点，而从一个页面到另一个页面的超链接则是这个网络的边。
微信好友的关系是相互的，如果我是你的好友，你也是我的好友。这样的网络称为无向网络(undirected graph/network)。但超链接并非如此，如果我的网站可以链接到维基百科，并不表示维基百科会链接到我的网站。这样的网络称为有向网络(directed graph/network)。
在图论和网络分析中，中心性（Centrality）是判断网络中节点重要性/影响力的指标。在社会网络分析中，一项基本的任务就是鉴定一群人中哪些人比其他人更有影响力，从而帮助我们理解他们在网络中扮演的角色。
那么，什么样的节点是重要的呢？
对节点重要性的解释有很多，不同的解释下判定中心性的指标也有所不同。
（1）点度中心性（degree centrality）
在无向网络中，我们可以用一个节点的度数（相当于你的微信好友数）来衡量中心性。在微博中，谢娜的粉丝数9千多万，她的点度中心性就很高。
这一指标背后的假设是：重要的节点就是拥有许多连接的节点。你的社会关系越多，你的影响力就越强。
图1：使用networkx绘制的蝴蝶结网络
在上面的蝴蝶结网络中，节点D的连接数是6，和网络中的所有人都建立了直接联系，其他节点的连接数都是3，因此节点D的点度中心性最高。整个网络一共有7个节点，意味着每个人最多可以有6个社会关系。因此，节点D的点度中心性是6/6=1，其他节点的点度中心性是3/6=0.5。
（2） 中介中心性（betweenness centrality）
网络中两个非相邻成员之间的相互作用依赖于其他成员，特别是两成员之间路径上的那些成员。他们对两个非相邻成员之间的相互作用具有控制和制约作用。Freeman (1979)认为中间成员对路径两端的成员具有“更大的人际关系影响”。因此，中介中心性的思想是：如果一个成员位于其他成员的多条最短路径上，那么该成员就是核心成员，就具有较大的中介中心性。
计算网络中任意两个节点的所有最短路径，如果这些最短路径中很多条都经过了某个节点，那么就认为这个节点的中介中心性高。回到上面的蝴蝶结网络，假设我们要计算节点D的中介中心性。
- 首先，我们计算节点D之外，所有节点对之间的最短路径有多少条，这里是15条（在6个节点中选择两个节点即节点对的个数）。
- 然后，我们再看所有这些最短路径中有多少条经过节点D，例如节点A要想找到节点E，必须经过节点D。经过节点D的最短路径有9条。
- 最后，我们用经过节点D的最短路径除以所有节点对的最短路径总数，这个比率就是节点D的中介中心性。节点D的中介中心性是9/15=0.6。
如果说点度中心性发现的是网络中的“名人”，那么中介中心性的现实意义是什么呢？
Maksim Tsvetovat&Alexander Kouznetsov在《社会网络分析》一书中有两个例子：
- 鲍勃徘徊在两个女人之间，他贪恋爱丽丝的美丽和谈吐，亦无法舍弃卡若琳娜的乐天和无忧无虑。但他必须小心谨慎，生怕自己在其中任何一个人面前露馅，这样的关系充满了压力和焦虑
- 银行家以5%的利率接受A公司的存款，以7%的利率贷款给B公司，这样的关系给银行家带来了巨大的利益。它的前提是，市场中的A公司和B公司不能直接接触，或至少无法轻易地找到对方
鲍勃和银行家的故事尽管截然不同，但他们都处于一种被称为被禁止的三元组(forbidden triad)的关系中，需要确保三元组的末端不能直接联系。没有联系就像网络中出现了一个洞，因此也被称为结构洞。
当网络中众多成员的接触或低成本接触都依赖我时，我就对其他成员有了控制和制约作用。我可以利用这种关系控制信息的流动，套取巨大的利益。当然，这样的关系也充满着压力和紧张。诚如Maksim Tsvetovat&Alexander Kouznetsov所言，商人的成功，不仅取决于他们对不对称信息的利用和经营能力，也需要对创造和维持套利机会带来的压力的高度容忍。
（3） 接近中心性（closeness centrality）
点度中心性仅仅利用了网络的局部特征，即节点的连接数有多少，但一个人连接数多，并不代表他/她处于网络的核心位置。接近中心性和中介中心性一样，都利用了整个网络的特征，即一个节点在整个结构中所处的位置。如果节点到图中其他节点的最短距离都很小，那么它的接近中心性就很高。相比中介中心性，接近中心性更接近几何上的中心位置。
假设我们要计算节点D的接近中心性，首先我们计算从节点D到所有其他节点的最短距离。从图中可以判断，节点D到所有其他节点的距离均为1，距离之和为6。因此，节点D的接近中心性为(7-1)/6=1。分子为网络中节点总数减去1。也就是说，如果一个人可以直接跟网络中所有其他人联系，那么他/她的接近中心性就是1。对于其他节点，如节点A的接近中心性为(7-1)/9=0.667。
接近中心性高的节点一般扮演的是八婆的角色（gossiper）。他们不一定是名人，但是乐于在不同的人群之间传递消息。
（4）特征向量中心性（eigenvector centrality）
特征向量中心性的基本思想是，一个节点的中心性是相邻节点中心性的函数。也就是说，与你连接的人越重要，你也就越重要。
特征向量中心性和点度中心性不同，一个点度中心性高即拥有很多连接的节点特征向量中心性不一定高，因为所有的连接者有可能特征向量中心性很低。同理，特征向量中心性高并不意味着它的点度中心性高，它拥有很少但很重要的连接者也可以拥有高特征向量中心性。
考虑下面的图，以及相应的5x5的邻接矩阵(Adjacency Matrix)，A。
邻接矩阵的含义是，如果两个节点没有直接连接，记为0，否则记为1。
现在考虑x，一个5x1的向量，向量的值对应图中的每个点。在这种情况下，我们计算的是每个点的点度中心性（degree centrality），即以点的连接数来衡量中心性的高低。
矩阵A乘以这个向量的结果是一个5x1的向量：
结果向量的第一个元素是用矩阵A的第一行去“获取”每一个与第一个点有连接的点的值（连接数，点度中心性），也就是第2个、第3个和第4个点的值，然后将它们加起来。
换句话说，邻接矩阵做的事情是将相邻节点的求和值重新分配给每个点。这样做的结果就是“扩散了”点度中心性。你的朋友的朋友越多，你的特征向量中心性就越高。
我们继续用矩阵A乘以结果向量。如何理解呢？实际上，我们允许这一中心性数值再次沿着图的边界“扩散”。我们会观察到两个方向上的扩散（点既给予也收获相邻节点）。我们猜测，这一过程最后会达到一个平衡，特定点收获的数量会和它给予相邻节点的数量取得平衡。既然我们仅仅是累加，数值会越来越大，但我们最终会到达一个点，各个节点在整体中的比例会保持稳定。
现在把所有点的数值构成的向量用更一般的形式表示：
我们认为，图中的点存在一个数值集合，对于它，用矩阵A去乘不会改变向量各个数值的相对大小。也就是说，它的数值会变大，但乘以的是同一个因子。用数学符号表示就是：
满足这一属性的向量就是矩阵M的特征向量。特征向量的元素就是图中每个点的特征向量中心性。
特征向量中心性的计算需要读者具备矩阵乘法和特征向量的知识，但不影响这里读者对特征向量中心性思想的理解，不再赘述。
（5）有向图与PageRank
PageRank是衡量有向网络中节点重要性的指标。
我们将万维网抽象成有向图：
（1）每个网页抽象成一个节点，假设有A、B、C、D四个节点；
（2）用户通过超链接在网页之间跳转，这种跳转是有方向的（directed），从网页A跳转到网页B不代表可以从网页B链接到网页A，这种节点之间的有方向的连接被抽象成有方向的边。整个网络构成一个有向图。
你可以很轻易地找到最受欢迎的网页。但是，PageRank的思想认为，指标最好还需要考虑到指向你的那些网页。也就是说，来自受欢迎的网页的跳转应该重于不太受欢迎的网页的跳转。这就是PageRank思想的精华，Google就是利用这一思想来给网站排名的。这里的思想依据和特征向量中心性其实是一致的。
首先，我们假设用户停留在一个页面时，跳转到每个链接页面的概率是相同的。例如，用户停留在页面A，他可以跳转到B、C、D三个页面，我们假设用户跳转到每个页面的概率相同，也就是说用户跳转到每个页面的概率均为1/3。我们可以用下面的转移矩阵（Transition Matrix）来表示整个有向图的情况：
假设有向图中有n个节点，那么M就是一个n行n列的矩阵，其中的第i行第j列代表从页面j跳转到页面i的概率。例如，M矩阵的第一行代表从ABCD跳转到页面A的概率。
然后，我们设每个页面的初始rank为1/4，4个页面的初始rank构成向量v：
用M第一行乘以向量v，得到的就是页面A最新rank的合理估计：0*1/4+1/2*1/4+0*1/4+1/2*1/4=1/4。Mv的结果就是ABCD四个页面的新rank：
然后用M再乘以新的rank向量，又会产生一个新的rank向量。迭代这一过程，Mv结果各个值的相对大小会保持稳定。也就是说，其结果等于用一个标量乘以v。
满足这一属性的向量就是矩阵M的特征向量。这里的结果会收敛在[1/4, 1/4, 1/5, 1/4]，这就是A、B、C、D最后的PageRank。这一结果表明，相比于网页C, ABD更为重要。
上述方程式假设上网者一定是通过网页上的链接进行跳转的，但实际上，上网者在每一步都有可能在地址栏随机输入一个网址，跳转到其他页面，而不是点击网页上的链接。或者，上网者可能到达一个没有任何链出页面的网页，这时他会随机到另外的页面进行浏览。
想象有两个网页的简单例子，网页A链接到B，但B无法链接到A。转移矩阵如下：
不断迭代，最后我们得到的是一个0矩阵：
考虑到B比A重要，这一结果是不合理的，它认为A和B同等重要。为了解决这个问题，我们引入“心灵运输”（Teleportation）的概念。它意味着上网者每一步都有可能随机输入一个网址（心灵运输），跳转到其他页面（这意味着每一步，网络上的每个网页都有一定的概率被访问到，它的概率为(1-d)/N，即上网者心灵运输的概率乘以每个网页被访问的概率），而不是点击网页上的链接。
我们假设上网者在任何页面继续向下浏览的概率为d=0.85。d也被称为阻尼系数（damping factor）。1-d=0.15就是上网者停止点击，随机跳到新网址的概率，即心灵运输的概率。设网页总数为N，那么跳转到任一网页的概率为N。因此，调整后的方程式如下：
其中的e为单位矩阵，这样才能与方程式的前半部分相加。
不断迭代后，两个网页的rank会收敛为：
（6）特征中心性小结
点度中心性：一个人的社会关系越多，他/她就越重要
中介中心性：如果一个成员处于其他成员的多条最短路径上，那么该成员就是核心成员
接近中心性：一个人跟所有其他成员的距离越近，他/她就越重要
特征向量中心性：与你连接的人社会关系越多，你就越重要
PageRank：来自受欢迎的网页的跳转应该重于不太受欢迎的网
原文链接：https://blog.csdn.net/hguisu/article/details/8013489
HITS（HITS(Hyperlink - Induced Topic Search) ） 算法是由康奈尔大学( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,为IBM 公司阿尔马登研究中心( IBM Almaden Research Center) 的名为“CLEVER”的研究项目中的一部分。
HITS算法是链接分析中非常基础且重要的算法，目前已被Teoma搜索引擎（www.teoma.com）作为链接分析算法在实际中使用。
（1）Hub页面与Authority页面
Hub页面（枢纽页面）和Authority页面（权威页面）是HITS算法最基本的两个定义。
所谓“Authority”页面，是指与某个领域或者某个话题相关的高质量网页，比如搜索引擎领域，Google和百度首页即该领域的高质量网页，比如视频领域，优酷和土豆首页即该领域的高质量网页。
所谓“Hub”页面，指的是包含了很多指向高质量“Authority”页面链接的网页，比如hao123首页可以认为是一个典型的高质量“Hub”网页。
图1给出了一个“Hub”页面实例，这个网页是斯坦福大学计算语言学研究组维护的页面，这个网页收集了与统计自然语言处理相关的高质量资源，包括一些著名的开源软件包及语料库等，并通过链接的方式指向这些资源页面。这个页面可以认为是“自然语言处理”这个领域的“Hub”页面，相应的，被这个页面指向的资源页面，大部分是高质量的“Authority”页面。
图1 自然语言处理领域的Hub页面
HITS算法的目的即是通过一定的技术手段，在海量网页中找到与用户查询主题相关的高质量“Authority”页面和“Hub”页面，尤其是“Authority”页面，因为这些页面代表了能够满足用户查询的高质量内容，搜索引擎以此作为搜索结果返回给用户。
（2）算法基本思想：相互增强关系
基本假设1：一个好的“Authority”页面会被很多好的“Hub”页面指向；
基本假设2：一个好的“Hub”页面会指向很多好的“Authority”页面；
（3）HITS算法与PageRank算法比较
HITS算法和PageRank算法可以说是搜索引擎链接分析的两个最基础且最重要的算法。从以上对两个算法的介绍可以看出，两者无论是在基本概念模型还是计算思路以及技术实现细节都有很大的不同，下面对两者之间的差异进行逐一说明。
1.HITS算法是与用户输入的查询请求密切相关的，而PageRank与查询请求无关。所以，HITS算法可以单独作为相似性计算评价标准，而PageRank必须结合内容相似性计算才可以用来对网页相关性进行评价；
2.HITS算法因为与用户查询密切相关，所以必须在接收到用户查询后实时进行计算，计算效率较低；而PageRank则可以在爬虫抓取完成后离线计算，在线直接使用计算结果，计算效率较高；
3.HITS算法的计算对象数量较少，只需计算扩展集合内网页之间的链接关系；而PageRank是全局性算法，对所有互联网页面节点进行处理；
4.从两者的计算效率和处理对象集合大小来比较，PageRank更适合部署在服务器端，而HITS算法更适合部署在客户端；
5.HITS算法存在主题泛化问题，所以更适合处理具体化的用户查询；而PageRank在处理宽泛的用户查询时更有优势；
6.HITS算法在计算时，对于每个页面需要计算两个分值，而PageRank只需计算一个分值即可；在搜索引擎领域，更重视HITS算法计算出的Authority权值，但是在很多应用HITS算法的其它领域，Hub分值也有很重要的作用；
7.从链接反作弊的角度来说，PageRank从机制上优于HITS算法，而HITS算法更易遭受链接作弊的影响。
8.HITS算法结构不稳定，当对“扩充网页集合”内链接关系作出很小改变，则对最终排名有很大影响；而PageRank相对HITS而言表现稳定，其根本原因在于PageRank计算时的“远程跳转”。