圖的基本概念
- 圖的定義
- 圖的數(shù)學(xué)表示
- 路徑
- 圖的連通性
- 最小生成樹
- 度眶俩，平均度
- 網(wǎng)絡(luò)的密度
- 網(wǎng)絡(luò)平均路徑長(zhǎng)度
- 網(wǎng)絡(luò)的聚類(clustering coefficient)系數(shù)
1. 圖(網(wǎng)絡(luò))的定義
定義：一個(gè)具體的網(wǎng)絡(luò)可以抽象為由一個(gè)點(diǎn)集和邊集組成的圖
， 如下圖1所示快鱼。以編程的角度來(lái)看，邊集和點(diǎn)集中的點(diǎn)可以稱之為一個(gè)對(duì)象（類）纲岭。
-
應(yīng)用價(jià)值：網(wǎng)絡(luò)這種數(shù)據(jù)結(jié)構(gòu)在很多方面都具有很強(qiáng)的應(yīng)用抹竹，如：
醫(yī)學(xué)專家希望了解傳染病在社會(huì)網(wǎng)絡(luò)中的傳播途徑并找到預(yù)防與控制策略
社會(huì)學(xué)家關(guān)心觀點(diǎn)和流言蜚語(yǔ)如何在社會(huì)網(wǎng)絡(luò)上進(jìn)行傳播
-
工程師希望找到由局部故障而引起大規(guī)模故障原因，如由美國(guó)次級(jí)房屋信貸危機(jī)而引起的全球金融危機(jī)
圖1 簡(jiǎn)單網(wǎng)絡(luò)拓?fù)鋱D.png
2. 圖的數(shù)學(xué)表示
定義：將圖表示為可以在計(jì)算機(jī)中處理的形式
-
常見表示方式：
- 鄰接矩陣
- 鄰接表
- 三元組
3. 路徑
定義：無(wú)向圖
其中每一對(duì)相鄰節(jié)點(diǎn)之間都存在著邊止潮，則稱P為節(jié)點(diǎn)
和節(jié)點(diǎn)
的一條路徑
-
含義：路徑在網(wǎng)絡(luò)的實(shí)際應(yīng)用中具有巨大的作用窃判，如：
- 社交網(wǎng)絡(luò)中，如果兩個(gè)節(jié)點(diǎn)之間沒(méi)有路徑則可以表示兩個(gè)人不相互認(rèn)識(shí)
- 在Internet中喇闸，如果兩個(gè)節(jié)點(diǎn)之間沒(méi)有路徑則可以表示這兩個(gè)PC之間不能進(jìn)行通信
問(wèn)1:如何求解兩個(gè)節(jié)點(diǎn)之間是否有路徑呢袄琳？如果有路徑的條數(shù)是多少询件？其中最短路徑的長(zhǎng)度及其序列是什么？
4. 圖的連通性
定義： 圖
含義：如一個(gè)Internet圖是連通的則表明圖中的每一個(gè)定點(diǎn)都能相互通信
問(wèn)2： 如何判斷一個(gè)圖是否是連通的，如果不連通又如何求解出最大連通圖逗旁？
5. 最小生成樹
定義：在有權(quán)無(wú)向（有向）連通圖
條邊使圖G連通并且
含義：最小生成樹表示的是使圖G連通的最小代價(jià)（邊數(shù)和權(quán)重）红伦，比如，在修路中淀衣，節(jié)點(diǎn)表示村莊昙读，道路表示邊。最小生成樹則可以表示使得所有村莊之間都連通時(shí)修建道路所耗費(fèi)最少的代價(jià)膨桥。從另一個(gè)角度來(lái)看蛮浑，最小生成樹象征著一個(gè)網(wǎng)絡(luò)的骨架。
6. 度国撵，平均度
- 定義：節(jié)點(diǎn)
的度表示與節(jié)點(diǎn)
表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度的平均值介牙。
7. 網(wǎng)絡(luò)的密度
定義：網(wǎng)絡(luò)的密度
等于網(wǎng)絡(luò)中實(shí)際的邊的個(gè)數(shù) / 網(wǎng)絡(luò)最大可能的邊數(shù)
含義：網(wǎng)絡(luò)的密度越大表示網(wǎng)絡(luò)的邊數(shù)越多壮虫，網(wǎng)絡(luò)的邊數(shù)越多則表示網(wǎng)絡(luò)越稠密，反之环础，則表示網(wǎng)絡(luò)越稀疏
8. 網(wǎng)絡(luò)平均路徑長(zhǎng)度
- 定義：節(jié)點(diǎn)
的距離
定義為連接這兩個(gè)節(jié)點(diǎn)的最短路徑上邊的數(shù)目囚似。網(wǎng)絡(luò)的平均路徑
定義為網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的距離的平均值，即
- 含義：六度空間理論线得，如社交網(wǎng)絡(luò)中饶唤，任意兩個(gè)人之間想取得聯(lián)系，則需要少于六個(gè)人進(jìn)行信息的傳遞即可
9. 網(wǎng)絡(luò)的聚類(clustering coefficient)系數(shù)
定義：網(wǎng)絡(luò)中有一節(jié)點(diǎn)
贯钩，那么在其所有的鄰居節(jié)點(diǎn)中募狂，有多少也是鄰居，即在你的兩個(gè)朋友中角雷，他們是否也是朋友祸穷。節(jié)點(diǎn)的聚類系數(shù)記為
,其中
是節(jié)點(diǎn)
含義：就社交網(wǎng)絡(luò)而言勺三，某一人的聚類系數(shù)可以表示該人朋友圈的緊密程度
networkx實(shí)現(xiàn)
-
圖的創(chuàng)建
-
圖的使用
問(wèn)題往往比答案更重要雷滚，以下所有實(shí)現(xiàn)都基于一個(gè)實(shí)際的問(wèn)題而言
# 圖的創(chuàng)建
# 1. 由圖的定義可知，圖由點(diǎn)集對(duì)象和邊集對(duì)象所組成吗坚。因此我們定義好點(diǎn)和邊即定義出一個(gè)圖祈远，定義一個(gè)圖1所示的圖
import networkx as nx
# 定義節(jié)點(diǎn)集
nodes = [1,2,3,4,5,6,7,8,9,10]
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10])
# 定義邊集
edges = [(1, 2),(1, 3),(1, 4),(1, 6),(2, 4),(2, 5),(3, 4),(3, 6),(4, 5),(4, 6),(4, 7),(5, 7),(6, 7),(6, 8),(7, 8),(8, 9)]
G.add_edges_from(edges)
# 圖的使用
# 定義節(jié)點(diǎn)集
nodes = [1,2,3,4,5,6,7,8,9,10]
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10])
# 定義邊集
edges = [(1, 2),(1, 3),(1, 4),(1, 6),(2, 4),(2, 5),(3, 4),(3, 6),(4, 5),(4, 6),(4, 7),(5, 7),(6, 7),(6, 8),(7, 8),(8, 9)]
G.add_edges_from(edges)
# 幫我看看1號(hào)節(jié)點(diǎn)有多少個(gè)朋友呆万？(判斷節(jié)點(diǎn)的度)
print('1號(hào)節(jié)點(diǎn)有%d個(gè)朋友'%G.degree(1))
# 幫我看看1號(hào)節(jié)點(diǎn)和10節(jié)點(diǎn)，9節(jié)點(diǎn)分別是不是朋友车份？（判斷節(jié)點(diǎn)之間是否有路徑）
print('1 和 9 是朋友') if nx.algorithms.shortest_paths.generic.has_path(G, 1, 9) else print('1 和 9 不是朋友')
print('1 和 10 是朋友') if nx.algorithms.shortest_paths.generic.has_path(G, 1, 10) else print('1 和 9 不是朋友')
# 幫我看看網(wǎng)絡(luò)中所有的節(jié)點(diǎn)能不能相互通信（判斷網(wǎng)絡(luò)是不是連通的）
print('網(wǎng)絡(luò)中所有的節(jié)點(diǎn)能相互通信')if approx.node_connectivity(G) == 0 else print('網(wǎng)絡(luò)中所有的節(jié)點(diǎn)不能相互通信')
# 幫我看看這個(gè)網(wǎng)絡(luò)的平均路徑長(zhǎng)度谋减，聚類系數(shù)？我等會(huì)有大用
print('聚類系數(shù)%f'%nx.algorithms.cluster.average_clustering(G))
print('平均路徑長(zhǎng)度%d'%nx.algorithms.shortest_paths.generic.average_shortest_path_length(G))
