Chapter7 圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型

數(shù)據(jù)分析與可視化第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.1有向圖和多重圖7.2圖的聚集系數(shù)7.3社會網(wǎng)絡(luò)分析7.4可平面圖的檢驗7.5有向無環(huán)圖的檢驗7.6最大流7.7隨機塊模型第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型2《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.1.1存儲圖數(shù)據(jù)7.1.2圖形展示7.1有向圖和多重圖3《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型連通圖（ConnectedGraph），節(jié)點（Node）（也可叫做一個頂點（Vertex）），連通路徑為一條邊（Edge）。如果只有單向連接，那么它就是有向圖（DirectedGraph）7.1有向圖和多重圖4《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.1.1存儲圖數(shù)據(jù)圖數(shù)據(jù)通常為鄰接矩陣，除非它是稀疏的。假設(shè)圖有V個節(jié)點，鄰接矩陣是有V行的矩陣。7.1有向圖和多重圖5《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型

ABCDEFA02526---B-085510-C26850--10D---0-11E---9088F---11880

芝加哥波士頓紐約華盛頓邁阿密達拉斯芝加哥01613-1145--波士頓16130338725--紐約-33803832145-華盛頓1145725383017092113邁阿密--2145170902161達拉斯---211321610鄰接矩陣1鄰接矩陣2importscipy.sparseassparsematrixA=sparse.lil_matrix((6,6))matrixA=sparse.lil_matrix([[0,25,26,0,0,0],[0,0,85,5,10,0],[26,85,0,0,0,10],[0,0,0,0,0,11],[0,0,0,9,0,88],[0,0,0,11,88,0]])print(matrixA)(0,1)25(0,2)26(1,2)85(1,3)5(1,4)10(2,0)26(2,1)85(2,5)10(3,5)11(4,3)9(4,5)88(5,3)11(5,4)887.1有向圖和多重圖6《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.1.2圖形展示igragh：提供多種格式，如GraphML、GML、LGL和NCOL僅完全支持DL文件格式優(yōu)點：便捷方式來配置和展示圖并將它們以SVG（ScalableVectorGraphics，可縮放圖形陣列）格式存儲，以便它們可以嵌入HTML文件7.1有向圖和多重圖7《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型使用igraph繪制星形圖7.1有向圖和多重圖8《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型fromigraphimport*vertices=["A","B","C","D","E","F","G","H","I","J"]edges=[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,1),(1,8),(8,2),(2,4),(4,9),(9,5),(5,7),(7,0)]graphStyle={'vertex_size':20}g=Graph(vertex_attrs={"label":vertices},edges=edges,directed=True)g.write_svg("simple_star.svg",width=500,height=300,**graphStyle)7.1有向圖和多重圖9《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型使用igraph繪制無向圖7.1有向圖和多重圖10《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型fromigraphimportreadg=read("./data/",format="pajek")g.vs["color"]="#3d679d"g.es["color"]="red"graphStyle={'vertex_size':12,'margin':6}#graphStyle["layout"]=g.layout("fr")#optionalg.write_svg("ragusa_graph.svg",width=600,height=600,**graphStyle)7.1有向圖和多重圖11《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型#設(shè)置圓形布局graphStyle["layout"]=g.layout("circle")7.1.2圖形展示NetworkX：用于網(wǎng)絡(luò)和圖形分析的庫找源節(jié)點到目的節(jié)點的最短路徑找度分布以繪制與交匯點相似的節(jié)點找圖的聚集系數(shù)7.1有向圖和多重圖12《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型使用NetworkX配置有向圖權(quán)重7.1有向圖和多重圖13《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型importmatplotlib.pyplotaspltimportpylabfrompylabimportrcParamsimportnetworkxasnximportnumpyasnp#設(shè)置圖形顯示尺寸為10英寸×10英寸（1英寸=2.54厘米）rcParams['figure.figsize']=10,10G=nx.DiGraph()#添加邊和權(quán)重G.add_edges_from([('K','I'),('R','T'),('V','T')],weight=3)G.add_edges_from([('T','K'),('T','H'),('I','T'),('T','H')],weight=4)G.add_edges_from([('I','R'),('H','N')],weight=5)G.add_edges_from([('R','N')],weight=6)7.1有向圖和多重圖14《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型#用這些值來決定節(jié)點的顏色val_map={'K':1.5,'I':0.9,'R':0.6,'T':0.2}values=[val_map.get(node,1.0)fornodeinG.nodes()]edge_labels=dict([((u,v,),d['weight'])foru,v,dinG.edges(data=True)])#設(shè)置邊的顏色red_edges=[('R','T'),('T','K')]edge_colors=['green'ifnotedgeinred_edgeselse'red'foredgeinG.edges()]pos=nx.spring_layout(G)nx.draw_networkx_edges(G,pos,width=2.0,alpha=0.65)nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)nx.draw(G,pos,node_color=values,node_size=1500,edge_color=edge_colors,edge_cmap=plt.cm.Reds)pylab.show()7.1有向圖和多重圖15《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型蛋白質(zhì)相互作用序列空間圖7.1有向圖和多重圖16《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型

7.2圖的聚集系數(shù)17《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型

importnetworkxasnxfrompylabimportrcParamsrcParams['figure.figsize']=12,12G=nx.read_gml('./data/lesmiserables.gml')G8=G.copy()dn=nx.degree(G8)forninlist(G8.nodes()):ifdn[n]<=8:G8.remove_node(n)pos=nx.spring_layout(G8)nx.draw(G8,node_size=10,edge_color='b',alpha=0.45,font_size=9,pos=pos)labels=nx.draw_networkx_labels(G8,pos=pos)18《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.2圖的聚集系數(shù)defvaluegetter(*values):iflen(values)==1:item=values[0]defg(obj):returnobj[item]else:defg(obj):returntuple(obj[item]foriteminvalues)returng19《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.2圖的聚集系數(shù)defclustering_coefficient(G,vertex):neighbors=G[vertex].keys()iflen(neighbors)==1:return-1.0links=0fornodeinneighbors:foruinneighbors:ifuinG[node]:links+=1ccoeff=2.0*links/(len(neighbors)*(len(neighbors)-1))returnlinks,len(neighbors),ccoeff20《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.2圖的聚集系數(shù)defcalculate_centrality(G):degc=nx.degree_centrality(G)nx.set_node_attributes(G,degc,'degree_cent')degc_sorted=sorted(degc.items(),key=valuegetter(1),reverse=True)forkey,valueindegc_sorted[0:10]:print("DegreeCentrality:",key,value)returnG,degcprint("Valjean",clustering_coefficient(G8,"Valjean"))print("Marius",clustering_coefficient(G8,"Marius"))print("Gavroche",clustering_coefficient(G8,"Gavroche"))print("Babet",clustering_coefficient(G8,"Babet"))print("Eponine",clustering_coefficient(G8,"Eponine"))print("Courfeyrac",clustering_coefficient(G8,"Courfeyrac"))print("Comeferre",clustering_coefficient(G8,"Combeferre"))calculate_centrality(G8)21《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.2圖的聚集系數(shù)#輸出的文本結(jié)果Valjean(82,14,0.9010989010989011)Marius(94,14,1.032967032967033)Gavroche(142,17,1.0441176470588236)Babet(60,9,1.6666666666666667)Eponine(36,9,1.0)Courfeyrac(106,12,1.606060606060606)Comeferre(102,11,1.8545454545454545)DegreeCentrality:Gavroche0.708333333333DegreeCentrality:Valjean0.583333333333DegreeCentrality:Enjolras0.583333333333DegreeCentrality:Marius0.583333333333DegreeCentrality:Courfeyrac0.5DegreeCentrality:Bossuet0.5DegreeCentrality:Thenardier0.5DegreeCentrality:Joly0.458333333333DegreeCentrality:Javert0.458333333333DegreeCentrality:Feuilly0.45833333333322《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.2圖的聚集系數(shù)#繪制的網(wǎng)格圖23《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.2圖的聚集系數(shù)《悲慘世界》人物關(guān)系圖

此時Comeferre恰好具有最大的聚集系數(shù)24《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.3社交網(wǎng)絡(luò)分析訪問流程：身份驗證→獲取確認鏈接例：訪問Twitter數(shù)據(jù)使用python-twitter，獲取、匯總數(shù)據(jù)存儲在cPickle中25《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.3社交網(wǎng)絡(luò)分析importcPickleimportos#使用方法#$設(shè)置CONSUMER_KEY,CONSUMER_SECRET,ACCESS_TOKEN_KEYS,ACCESS_TOKEN_SECRET#作為環(huán)境變量#$pythonget_data.py#downloadsfriendandfollowerdatato./data#在運行時看到的錯誤#raiseURLError(err)#urllib2.URLError:<urlopenerror[Errno104]Connectionresetbypeer>DATA_DIR="data"#好友/關(guān)注者數(shù)據(jù)的存儲目錄#我們要分析的網(wǎng)名列表screen_names=['KirthiRaman','Lebron']26《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.3社交網(wǎng)絡(luò)分析defget_filenames(screen_name): """Buildthefriendsandfollowersfilenames""" returnos.path.join(DATA_DIR,"%s.friends.pickle"%(screen_name)),os.path.join(DATA_DIR,"%s.followers.pickle"%(screen_name))if__name__=="__main__": #登錄賬戶

t=twitter.Api(consumer_key='k7atkBNgoGrioMS...',consumer_secret='eBOx1ikHMkFc...', access_token_key='8959...', access_token_secret='O7it0...');printt.VerifyCredentials()

27《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.3社交網(wǎng)絡(luò)分析forscreen_nameinscreen_names:fr_filename,fo_filename=get_filenames(screen_name) print"Checkingfor:",fr_filename,fo_filename ifnotos.path.exists(fr_filename): print"Gettingfriendsfor",screen_name fr=t.GetFriends(screen_name=screen_name) cPickle.dump(fr,open(fr_filename,"w"),protocol=2) ifnotos.path.exists(fo_filename): print"Gettingfollowersfor",screen_name fo=t.GetFollowers(screen_name=screen_name) cPickle.dump(fo,open(fo_filename,"w"),protocol=2)

pythonget_data.pypythonsummarise_data.pypythondraw_network.py28《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.3社交網(wǎng)絡(luò)分析運行結(jié)果如圖：圖Twitter網(wǎng)絡(luò)中粉絲信息29《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.4可平面圖的檢驗定義：可以在沒有任何相交的邊的平面上繪制的圖繪制時必須從一個節(jié)點開始，從一條邊繪制到另一條邊，并在繼續(xù)繪制時跟蹤這些面可平面圖示例30《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.4可平面圖的檢驗

圖可平面圖示例31《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.4可平面圖的檢驗importplanarityimportnetworkxasnx#8個節(jié)點的完整圖，G8G8=plete_graph(8)#G8不是可平面圖print(planarity.is_planar(G8))#將顯示錯誤，因為G8不是可平面圖K=planarity.kuratowski_subgraph(G8)#將顯示邊print(K.edges())#將顯示圖nx.draw(G8)False[(0,4),(0,5),(0,7),(2,4),(2,5),(2,7),(3,5),(3,6),(3,7),(4,6)]32《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.4可平面圖的檢驗完全圖該示例說明下圖包含8個節(jié)點的完全圖不是可平面圖33《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.5有向無環(huán)圖的檢驗有向無環(huán)圖（DirectedAcyclicGraph，DAG）定義：從給定節(jié)點A到B的邊將指向特定方向（A→B或B→A）并且是無環(huán)的，同時，它們不會循環(huán)例：字典樹34《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.5有向無環(huán)圖的檢驗importmatplotlib.pyplotaspltimportpylabfrompylabimportrcParamsimportnetworkxasnximportnumpyasnp#設(shè)置圖形顯示尺寸為10×10英寸rcParams['figure.figsize']=10,10G=nx.DiGraph()#添加邊和權(quán)重G.add_edges_from([('K','I'),('R','T'),('V','T')],weight=3)G.add_edges_from([('T','K'),('T','H'),('T','H')],weight=4)#用這些值來決定節(jié)點的顏色val_map={'K':1.5,'I':0.9,'R':0.6,'T':0.2}values=[val_map.get(node,1.0)fornodeinG.nodes()]35《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.5有向無環(huán)圖的檢驗edge_labels=dict([((u,v,),d['weight'])foru,v,dinG.edges(data=True)])#設(shè)置邊顏色red_edges=[('R','T'),('T','K')]edge_colors=['green'ifnotedgeinred_edgeselse'red'foredgeinG.edges()]pos=nx.spring_layout(G)nx.draw_networkx_edges(G,pos,width=2.0,alpha=0.65)nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)nx.draw(G,pos,node_color=values,node_size=1500,edge_color=edge_colors,edge_cmap=plt.cm.Reds)pylab.show()nx.is_directed_acyclic_graph(G)True36《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.5有向無環(huán)圖的檢驗該示例中的有向無環(huán)圖：有向無環(huán)圖37《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.6最大流定義：流向圖是從源到目的地的有向圖，其容量沿每條邊分配邊應(yīng)當有容量，表明該邊最多可以支持多少流量。如果該容量不存在，則假定它具有無限容量流向圖示例38《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.6最大流代碼示例：importnetworkxasnxG=nx.DiGraph()G.add_edge('p','y',capacity=5.0)G.add_edge('p','s',capacity=4.0)G.add_edge('y','t',capacity=3.0)G.add_edge('s','h',capacity=5.0)G.add_edge('s','o',capacity=4.0)flow_value=nx.maximum_flow_value(G,'p','o')print("Flowvalue",flow_value)nx.draw(G,node_color='#a0cbe2')Flowvalue4.0使用NetworkX包中maximum_flow_value(Graph,from,to)39《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.6最大流流向圖40《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.7隨機塊模型簡單定義：以標量n為特征。這表示組的數(shù)量或集群的數(shù)量，以及顯示節(jié)點和其連接的矩陣PyMC包：提供馬爾可夫鏈蒙特卡羅(MarkovChainMonteCarlo，MCMC)和3個概率模型構(gòu)建塊的包StochPy包：可用于隨機建模41《數(shù)據(jù)分析與可視化》第七章圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)模型7.7隨機塊模型importpymcasmcfrompylabimportrcParams#