1. Johngo学长首页
  2. 技术点详细复盘专题
  3. 人工智能

【图分析】逼近（Approximation）

• 人工智能 • 阅读 95

目录

*
– Connectivity
– K-Components
– Clique,apx-maximum independent set
– Clique,max clique
– Clustering,clustering_coefficient
– Diameter
– Dominating Set
– Matching
– Ramsey
– Steiner Tree
– Traveling Salesman
–
+ Travelling Salesman Problem(TSP)
– Treewidth
– Vertex Cover
– Max Cut

Connectivity

计算图G G G的连通性，或者是G G G中点与点之间的连通性。

K-Components

K – 连通分量，计算图G G G中存在的1-连通分量，2-连通分量，…，k-连通分量。

{"1": [["p6", "p7", "p5", "p2", "p4", "p3", "p1"]], "2": [["p6", "p7", "p5"], ["p3", "p2", "p1", "p4"]]}

Clique,apx-maximum independent set

独立集，图G G G中任意两个顶点都不相连的顶点集合，例如二分图：

【图分析】逼近（Approximation）
{1，2，3}、{4，5，6}等等，而{1，2}也是独立集，但不是最大的独立集。

; Clique,max clique

最大分团指的是图G = ( V , E ) G=(V,E)G =(V ,E )，的最大子集C C C，这个子集中的每个节点都是两两相连的（完全图）。

Clustering,clustering_coefficient

群聚系数用来描述图中的顶点之间集结成团的程度的系数。也就是一个点的相邻点之间相互连接的程度。

global clustering coefficient（全局集聚系数）
假设有图G = ( V , E ) G=(V,E)G =(V ,E )，L ( i ) L(i)L (i )表示与节点v i v_i v i ​相连的边的集合：L ( i ) = { v j : e i j ∈ E ∩ e j i ∈ E } L(i)={v_j:e_{ij}\in E\cap e_{ji}\in E }L (i )={v j ​:e ij ​∈E ∩e ji ​∈E }，L ( i ) L(i)L (i )里边的数量就是节点v i v_i v i ​的度，记作k i : k i = ∣ L ( i ) ∣ k_i:k_i=|L(i)|k i ​:k i ​=∣L (i )∣
如果用C t o t a l ( G ) C_{total}(G)C t o t a l ​(G )表示全局集聚系数，G Δ G_\Delta G Δ​表示闭三元组的个数，G ∧ G_\wedge G ∧​表示开三元组的个数（一个三元组是其中有两条（开三元组）或三条（闭三元组）无向边连接的三个结点）。全局集聚系数是所有三元组（包括开和闭的）中封闭三元组数目的比例：
C t o t a l ( G ) = 3 ∗ G Δ 3 ∗ G Δ + 2 ∗ G ∧ C_{total}(G)=\frac{3G_\Delta}{3G_\Delta+2*G_\wedge}C t o t a l ​(G )=3 ∗G Δ​+2 ∗G ∧​3 ∗G Δ​​

local clustering coefficient（局部集聚系数）
图中一个节点的局部集聚系数表示它的相邻节点形成一个团（完全图）的紧密程度。结点v i v_i v i ​的局部集聚系数C i C_i C i ​是它的相邻结点之间的连接数与它们所有可能存在连接的数量的比值。有向图的局部集聚系数为
C i = ∣ { e j k } ∣ k i ( k i − 1 ) , v j , v k ∈ N i , e j k ∈ E C_i=\frac{|{e_{jk}}|}{k_i(k_i-1)},v_j,v_k\in N_i,e_{jk}\in E C i ​=k i ​(k i ​−1 )∣{e jk ​}∣​,v j ​,v k ​∈N i ​,e jk ​∈E
其中，N i N_i N i ​是节点v i v_i v i ​的相邻节点。无向图的局部集聚系数为
C i = 2 ∣ { e j k } ∣ k i ( k i − 1 ) , v j , v k ∈ N i , e j k ∈ E C_i=\frac{2|{e_{jk}}|}{k_i(k_i-1)},v_j,v_k\in N_i,e_{jk}\in E C i ​=k i ​(k i ​−1 )2∣{e jk ​}∣​,v j ​,v k ​∈N i ​,e jk ​∈E
average clustering coefficient（平均集聚系数）
定义为所有节点的局部集聚系数的均值
C ‾ = 1 n ∑ i = 1 n C i \overline{C}=\frac{1}{n}\displaystyle\sum_{i=1}^{n}C_i C =n 1 ​i =1 ∑n ​C i ​
有更高平均集聚系数的G G G有着模块结构，在不同节点间有更小的平均距离。

Diameter

可以使用2-sweep算法计算无向图的直径，而使用2-dSweep算法计算有向图的直径。

Dominating Set

点支配集（dominating set）
假设G = ( V , E ) G=(V,E)G =(V ,E )是一个简单无向图，S ⊆ V , S ≠ ∅ S\subseteq V,S\neq\varnothing S ⊆V ,S =∅，如果∀ v ∈ V − S \forall v\in V-S ∀v ∈V −S，S S S都有至少一个节点与v v v相邻，则称S S S是G G G的支配集（dominating set）

边支配集（edge dominating set）
假设G = ( V , E ) G=(V,E)G =(V ,E )是一个简单无向图，F ⊆ E , F ≠ ∅ F\subseteq E,F\neq\varnothing F ⊆E ,F =∅，如果∀ e ∈ E − F \forall e\in E-F ∀e ∈E −F，F F F都有至少一条边的节点与e e e的节点重合。则称F F F是G G G的边支配集（edge dominating set）

Matching

minimum maximal matching
在一个无向图G G G中，找到一个边集S S S，这个边集拥有最少的边，这些边能够覆盖G G G中尽可能多的节点。这些边不会共有某个节点。

【图分析】逼近（Approximation）

; Ramsey

待补充

Steiner Tree

metric closure
metric closure（度量闭包）是关于G G G的一个完全图（每个节点都与其他节点相连），这个图的每一条边的权重都由原图G G G的权重计算得到（networkx里是weight属性）。
如下原数据

{
  "node_title": ["id","name","age"],
  "node_title_type": ["string","string","string"],
  "nodes": [
    ["p1","Tayler","32"],
    ["p2","Marco","31"],
    ["p3","Mike","30"],
    ["p4","Lily","26"],
    ["p5","Andy","24"],
    ["p6","Anne","24"],
    ["p7","Ardy","24"],
    ["p8","Andis","24"]
  ],
  "link_title": ["src","dst","name","weight","sdate","edate"],
  "link_title_type": ["string","string","int","string","date","date"],
  "links": [
    ["p1","p2","friend",30,"2010-08-09","2021-08-09"],
    ["p1","p3","friend",25,"2010-08-09","2021-08-09"],
    ["p2","p4","friend",20,"2010-08-09","2021-08-09"],
    ["p4","p5","friend",36,"2010-08-09","2021-08-09"],
    ["p3","p4","friend",40,"2010-08-09","2021-08-09"],
    ["p5","p6","friend",40,"2010-08-09","2021-08-09"],
    ["p6","p7","friend",40,"2010-08-09","2021-08-09"],
    ["p5","p7","friend",40,"2010-08-09","2021-08-09"],
    ["p6","p8","friend",40,"2010-08-09","2021-08-09"]
  ]
}

计算得到的完成图的边的值为：

{
    "p1":{
        "p4":{
            "distance":50,
            "path":["p1","p2","p4"]
        },
        "p2":{
            "distance":30,
            "path":["p1","p2"]
        },

        ...............

    }
}

从结果来看，p1和p4之间的边的权重（distance）由原图G G G中( p 1 , p 2 ) (p1,p2)(p 1 ,p 2 )的权重w p 1 p 2 w_{p1p2}w p 1 p 2 ​和( p 2 , p 4 ) (p2,p4)(p 2 ,p 4 )的权重w p 2 p 4 w_{p2p4}w p 2 p 4 ​相加得到。

steiner tree

最小斯坦纳树（the minimum Steiner tree）是图G G G中的一棵树，这棵树覆盖了指定的一些点（一般作为参数传入，称为terminal nodes），并且这棵树覆盖的边的权重和最小。

Traveling Salesman

Travelling Salesman Problem(TSP)

TSP问题是希望从图G G G中寻找一条路径，salesman通过这条路径行走可以经过G G G中的所有节点。路径需要满足以下条件：
（1）路径的距离最短。
（2）这条路径起始点和终点是同一个节点。
（3）salesman在行走时只会经过一次节点。
求解TSP问题有四种方法，christofides，greedy_tsp，simulated_annealing_tsp，threshold_accepting_tsp。

christofides 算法

【图分析】逼近（Approximation）

greedy_tsp算法
greedy指的是贪心算法（greedy algorithm），该算法是指：在对问题求解时，总是做出当前情况下的最好选择。这种最好的选择一般都是局部最优解，不具备后效性，针对TSP问题，贪心算法的求解过程为：
（1）从某一个城市开始，每次选择一个城市，直到走完所有的城市。
（2）每次在选择下一个城市的时候，只考虑当前情况，保证当前经过的路径总距离最小。
假设城市使用数字编号来表示：1 , 2… , N 1,2…,N 1 ,2…,N，任何两个城市的距离记录在数组d [ i , j ] d[i,j]d [i ,j ]中。依次访问过的城市编号被记录在s [ 1 ] , s [ 2 ] , . . . , s [ N ] s[1],s[2],…,s[N]s [1 ],s [2 ],…,s [N ]中，即第i i i次访问的城市记录在s [ i ] s[i]s [i ]中。
算法的伪代码如下：

(1)s[1]=1
(2)sum=0
(3)initialize the distance array d[i,j]
(4)i=2
(5)search the nearest city j(unvisited) to s[i-1]，get d[i,j]
(6)sum = sum + d[i,j]
(7)s[i]=j
(8)i=i+1
(9) if iN,goto(5),else,goto(10)
(10)print s[N]
(11)print sum

simulated_annealing_tsp算法
待补充

threshold_accepting_tsp算法
待补充

Treewidth

图的树分解及树宽
设G ( V , E ) G(V,E)G (V ,E )是一个无向图，则图G G G的树分解由树T T T和T T T的每一个节点t t t关联的子集X t ⊆ V X_t\subseteq V X t ​⊆V构成（此时可称这些子集X t X_t X t ​是树分解的片段）。树T T T和片段集{ X t , t ∈ T } {X_t,t\in T}{X t ​,t ∈T }满足以下3个条件：

（1）⋃ ( X t , t ∈ T ) = V \bigcup (X_t,t\in T)=V ⋃(X t ​,t ∈T )=V，即全部片段集X t X_t X t ​中包含的节点涵盖了图G G G的所有节点，或者说图G G G的每个节点至少属于某一个片段X t X_t X t ​。
（2）对图G G G的每一条边e ∈ E e\in E e ∈E，至少存在一个片段X t X_t X t ​，包含e e e的两个端点。
（3）若t 1 , t 2 , t 3 t_1,t_2,t_3 t 1 ​,t 2 ​,t 3 ​是树T T T的3个节点，其中t 2 t_2 t 2 ​在t 1 t_1 t 1 ​到t 3 t_3 t 3 ​的路径上，那么，若G G G的节点v v v属于X t 1 X_{t1}X t 1 ​和X t 3 X_{t3}X t 3 ​，则v v v一定属于X t 2 X_{t2}X t 2 ​

树分解的宽度等于m a x ( ∣ X t ∣ − 1 , t ∈ T ) max(|X_t|-1,t\in T)ma x (∣X t ​∣−1 ,t ∈T )。图G G G的树宽就是G G G的最小树分解的宽度，即在图G G G的所有树分解中，具有最小宽度的树分解的宽度称为图G G G的树宽。

Vertex Cover

待补充

Max Cut

待补充

Original: https://blog.csdn.net/sword_csdn/article/details/120087232
Author: sword_csdn
Title: 【图分析】逼近（Approximation）

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/557220/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球