python子图之间的距离_python与图论的桥梁——igraph
之前收集到一個(gè)關(guān)于紐約市全年出租車的數(shù)據(jù)集，于是想到，我們是不是可以用這個(gè)數(shù)據(jù)集來研究一下紐約市中各個(gè)社區(qū)之間的關(guān)聯(lián)度？為了研究這個(gè)問題，就需要使用python來建立一些圖論模型。
igraph是python/R等語言中常用的建立圖模型的模塊。接下來首先對igraph模塊做一個(gè)簡要介紹，然后對紐約市的出租車數(shù)據(jù)進(jìn)行建模。
一、igraph
首先我們導(dǎo)入所需的包
import pandas as pd import numpy as np import matplotlib.pyplot as plt from igraph import * import datetime創(chuàng)建圖：
g = Graph()print一下：
print(g) #輸出結(jié)果如下 #IGRAPH U--- 0 0 --添加頂點(diǎn)：
g.add_vertices(3) print(g) #輸出結(jié)果如下 #IGRAPH U--- 3 0 --添加邊：
g.add_edges([(0,1), (1,2)])IGRAPH U--- 3 2 -- + edges: 0--1 1--2如果我們想要?jiǎng)h去某兩個(gè)節(jié)點(diǎn)間的邊：
g.get_eid(2,1)#獲取邊的序號 #1 g.delete_edges(1)#刪除邊 print(g) """ IGRAPH U--- 3 1 -- + edges: 0--1 """我們還可以給邊定義一些屬性
如：
g.vs["name"] = ["Alice"] g.vs["age"] = [25] g.vs["gender"] = ["f"] g.es["is_formal"] = [False]此時(shí)的圖如下：
""" IGRAPH UN-- 3 1 -- + attr: age (v), gender (v), name (v), is_formal (e) + edges (vertex names): Alice--Alice """二、Community Detection(社區(qū)發(fā)現(xiàn))
1.什么是community(社區(qū))
community是一個(gè)圖中的一個(gè)子圖，它包含比圖的其余部分或更緊密地彼此緊密鏈接的節(jié)點(diǎn)，如果子圖內(nèi)部的邊數(shù)大于這些子圖之間的邊數(shù)，則圖具有community結(jié)構(gòu)。
例如：
community structure以及：
community structure2.什么是modularity(模塊度)
Newman 在2003年的論文 “Finding and evaluating community structure in networks” 中首次提出了modularity的定義，它被用來度量自己的社團(tuán)檢測算法的好壞。
Consider a particular division of a network into k communities. Let us define a k×k symmetric matrix e whose element is the fraction of all edges in the network that link vertices in community i to vertices in community j [49].假設(shè)社團(tuán)劃分把一個(gè)網(wǎng)絡(luò)劃分為
個(gè)社團(tuán)，定義一個(gè) 的矩陣 , 表示連接社團(tuán) 和社團(tuán) 的邊的數(shù)目占總邊數(shù)的比例。特別的，
表示的是社團(tuán) 和社團(tuán) 之間的邊占總邊數(shù)的比例，也就是社團(tuán) 內(nèi)部的邊占總邊數(shù)的比例。以下便是模塊度的計(jì)算公式：
如果用
表示社團(tuán) 內(nèi)部的邊數(shù)，則 。然后把 代入，就可以得到計(jì)算modularity最常用的公式3.multilevel community detection algorithm
為了快速進(jìn)行社區(qū)發(fā)現(xiàn)，我們需要一些求解該問題的算法。這其中，時(shí)間復(fù)雜度最低的便是Blondel發(fā)明的multilevel算法。
該算法有兩個(gè)主要步驟：
步驟一：
不斷地遍歷網(wǎng)絡(luò)圖中的節(jié)點(diǎn)，通過比較節(jié)點(diǎn)給每個(gè)鄰居社區(qū)帶來的模塊度的變化，將單個(gè)節(jié)點(diǎn)加入到能夠使modulaity模塊度有最大增量的社區(qū)中。
（比如節(jié)點(diǎn)
步驟二：
對第一階段進(jìn)行處理，將屬于同一社區(qū)的頂點(diǎn)合并為一個(gè)大的超點(diǎn)重新構(gòu)造網(wǎng)絡(luò)圖，即一個(gè)社區(qū)作為圖的一個(gè)新的節(jié)點(diǎn)。此時(shí)兩個(gè)超點(diǎn)之間邊的權(quán)重是兩個(gè)超點(diǎn)內(nèi)所有原始頂點(diǎn)之間相連的邊權(quán)重之和，即兩個(gè)社區(qū)之間的邊權(quán)重之和。
重復(fù)以上步驟，直至不能改變網(wǎng)絡(luò)圖為止。
三、實(shí)例
通過紐約的出租車數(shù)據(jù)進(jìn)行紐約市的社區(qū)發(fā)現(xiàn)。
首先讀取數(shù)據(jù)
intersections=pd.read_csv("intersections.csv",header=None) intersection_to_zone=pd.read_csv("intersection_to_zone.csv") taxi_id=pd.read_csv("taxi_id.csv",header=None)觀察數(shù)據(jù)
taxi_id.tail(5)每一趟出租車的數(shù)據(jù)intersection_to_zone.tail(5)每個(gè)intersection屬于的communityintersections.head(5)intersection的經(jīng)緯信息建立圖模型，并遍歷taxi數(shù)據(jù)，探究早晨7-9點(diǎn)的紐約哪些社區(qū)的關(guān)系較為緊密
g1=Graph() g1.add_vertices(63) for index, row in taxi_id.iterrows():beginTime = datetime.datetime.fromtimestamp(row["1"])endTime = datetime.datetime.fromtimestamp(row["2"])start_place=row["3"]end_place=row["4"]print(beginTime)try:start_zone=dic[start_place]end_zone=dic[end_place]except KeyError:continueif (beginTime.hour==7 or beginTime.hour==8) and (endTime.hour==7 or endTime.hour==8):#print(start_zone,end_zone)g1.add_edges([(to_vid[start_zone],to_vid[end_zone])])使用Blondel的算法進(jìn)行社區(qū)發(fā)現(xiàn)
result1=g1.community_multilevel()觀察結(jié)果
print(result1)Clustering with 63 elements and 3 clusters [0] 0, 1, 2, 7, 13, 14, 15, 18, 19, 20, 23, 26, 31, 32, 35, 41, 42, 43, 44,45, 48, 49, 50, 51, 59, 60 [1] 8, 9, 10, 16, 17, 36, 37, 38, 39, 47, 58 [2] 3, 4, 5, 6, 11, 12, 21, 22, 24, 25, 27, 28, 29, 30, 33, 34, 40, 46, 52,53, 54, 55, 56, 57, 61, 62可以看到，該算法將紐約劃分為了三個(gè)主要部分。
同時(shí)，結(jié)合紐約的地理信息
可見紐約的五個(gè)區(qū)分布在三塊分離的島嶼上，而出租車數(shù)據(jù)的分析結(jié)果也與這一點(diǎn)吻合的很好。
看完文章別忘了送上點(diǎn)贊~
歡迎關(guān)注我的個(gè)人公眾號-leo的學(xué)習(xí)之旅
公眾號內(nèi)會分享個(gè)人整理/學(xué)習(xí)的數(shù)據(jù)科學(xué)/深度學(xué)習(xí)知識~
總結(jié)
以上是生活随笔為你收集整理的python子图之间的距离_python与图论的桥梁——igraph的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
