1樓：核桃丫
最近在gitlab上發現了乙個可以算graph相似度的package，用graph kernel方法。挺有意思的，樓主可以去試試看
2樓：方軒固
剛好上advanced machine learning 時老師帶了一下這個話題，強答一番。不少答主已經說了graph kernel， 排名第二的答主也提到了random walk。此處稍微直觀地展示下。
其實想法很直觀：在圖上做random walk， 然後統計各節點被訪問的頻率。如果兩個圖中各節點的被訪問頻率的pattern 很相近，那麼就判定這兩個圖是相似度高。
具體細節感興趣的同學可以自己google。
直接放那張ppt吧。
3樓：
看了樓上的某些答案覺得不能忍，來說兩句吧。。
簡而言之worst case這是個NP-hard的問題，因為如果想比較兩個圖的相似性，必須先有乙個好的node matching，沒有seed nodes並且圖沒有特定結構的時候，估計這個matching本身就是NP-hard的問題。
如果registration problem已經解決，就是已知了nodes的一一對應，那麼就有很多方法可以做了。比如graphon estimation，然後兩個denoise的圖直接相減算distance；或者你可以fit乙個low rank模型，給每乙個node乙個profile，然後比較兩個圖的node profiles，可選的模型包括stochastic block model, latent space model (詳情見Peter Hoff, Cosma Shalizi他們的工作)；甚至我在想是不是可以直接兩圖adjacency相減，然後看largest eigenvalue，做乙個test，看減出來的圖是不是element-wise mean zero，像近期出現的一篇文章那樣……
總之如果有registration這個問題就很簡單，基本隨意了；沒有的話就很難，目前還沒有比較靠譜的polynomial時間的演算法
4樓：shihang Wen
最近剛剛在做複雜網路這一部分的內容，想著可以回答一下。我主要研究的有兩個：jaccard相似性和cosine余弦相似性。
Jaccard 相似性：
Jaccard相似性用來衡量兩個集合之間的相似程度，被定義為是兩個集合交集的元素的個數除以兩個集合並集元素的個數。
其中，集合A，B既可以是邊的集合，也可以是點的集合。
余弦相似度：
通過測量兩個向量的夾角的余弦值來度量它們之間的相似性。0度角的余弦值是1，而其他任何角度的余弦值都不大於1；並且其最小值是-1。從而兩個向量之間的角度的余弦值確定兩個向量是否大致指向相同的方向。
兩個向量有相同的指向時，余弦相似度的值為1；兩個向量夾角為90°時，余弦相似度的值為0；兩個向量指向完全相反的方向時，余弦相似度的值為-1。這結果是與向量的長度無關的，僅僅與向量的指向方向相關。余弦相似度通常用於正空間，因此給出的值為0到1之間。
Bargigli L, Di Iasio G, Infante L, et al. The multiplex structure of interbank networks[J]. Quantitative Finance, 2015, 15(4):
673-691.
5樓：
從CS的角度，目前的演算法大致上是通過 graph matching，graph alignment，graph kernel 或者 feature extraction 來比較圖的相似度。可以參考14年ICDM的tutorial：Tutorial - ICDM 2014
6樓：Yifan
作為純數出身的人，從數學角度思考題主的問題。如果是喜歡圖論又關注數學的人，應該聽說過近幾年的熱點方向：「graph limit」。
數學界三大獎之一沃爾夫獎獲得者，L. Lovasz[1]對這個方向做出了很大貢獻，並且graph limit無論是在數論，分析，概率這些純數方向，還是CS，演算法這些應數方項都有很多應用。
極限的定義大家都知道，不嚴謹的說極限是描述一種無限接近的狀態，那graph limit不可避免的要定義不同的圖之間的距離。從幾何上考慮，如果要定義兩個圖G和H距離很近，那麼他們應該在區域性足夠相似。也就是說如果我從G上面撕下來一塊相對大的碎片，那我應該能從H上找到乙個區域性和我剛撕下來的那塊graph很「幾乎同構」。
用數學的語言描述，首先定義圖F到G同構的個數，然後定義同構密度，於是，。
如果稍微思考幾秒鐘我上面說的話，你就會發現..我說的是廢話。因為這個定義只是直觀的幾何描述，對解決問題沒有任何幫助。..
接下來是正經的定義（雖然實際上和上面的直觀定義是一回事）。首先對於兩個定義在同乙個點集上的圖，直觀的看，如果我們從中找任意兩個子集，這兩個子集之間的邊的數量在上差不多，我們就可以認為這兩個圖很相似。也就是說，定義是圖中之間的邊的數量，我們用描述兩個圖的距離。
我們把這種距離叫做cut distance。注意的是這個定義也在adjacency matrix上有良好的表示。
有了這個定義，那麼對於擁有相同vertex數但是不同點集的兩個圖，我們可以對其中乙個圖重新編號；對於vertex數不同的兩個圖，我們可以blow-up。比較令人驚訝的是，這樣得來的距離定義和我們一開始的直觀定義相同。
接下來，這個距離的定義有什麼用？
我注意到題主貌似是cs的，那我著重說一下我了解的cs方向的應用。作為背景，Szemeredi's regularity lemma目前是圖論中最重要的定理之一，同時在數論，分析，概率，理論CS中有非常多的應用。粗略的說，這個引理描述的是每個很大的圖都可以被劃分為幾部分，使得幾乎任意兩部分形成的二部圖「random-like」。
大概在95年左右，Friez和Kannan做出了乙個regularity lemma的弱化版本，目前稱為FK-regularity lemma（或者weak regularity lemma）：他們構造了乙個的演算法，input任意乙個非常大的圖（有個點 ），output乙個非常regular的圖，使得。
有了這個定理，我們可以快速（）的找到很多NP問題的近似解。這個方向的研究現在非常活躍。舉個例子，判定乙個圖是否包含子圖是至少NP-complete的，但是我們可以快速找出圖中子圖的近似數量[2]。
找到乙個圖的rectilinear crossing number是NP-hard的，但是我們可以快速找出他的近似值，甚至可以給出乙個構造[3]。大致思路很簡單，給定乙個大圖，先作用FK演算法找到乙個劃分，我們先遍歷小圖（constant time），然後再blow-up，利用兩個圖cut-distance相近來近似得到的結果。
強調一下這個方法我認為應該只對dense graph有效。對於稀疏圖，我們的近似太粗暴了。L.
Lovasz[1]最近倒是有研究graphs with bounded degree這種相對稀疏的圖，不過具體方法不是很了解，大家有興趣可以看參考資料。
Reference
[1]. L. Lovasz, Large networks and graph limits, American Mathematical Society, 2012.
7樓：呆思
Nature communication 和 physical review x近期都有衡量兩個網路相似性的工作發表，具體忘了文章名字了
8樓：豬鼻蛇
GRAPH MATCHING AND LEARNING IN PATTERN RECOGNITION IN THE LAST 10 YEARS
9樓：冰室
我覺得這個問題需要乙個更明確的語境:比如說一種問題是我們已有乙個圖G1到G2的點的一一對應關係，基於這個對應關係來計算圖的關係，比如說兩個物種的同源因子的對應，那麼圖和圖的距離可以用rewiring操作的次數來計算，類似於進化樹構建演算法中使用的幾種距離（樹也是一種特殊的圖）。但是另一種問題更複雜一些，就是只給兩個圖，而沒有乙個一一對應關係。
我們也可以計算某種距離，但我不知道有什麼樣的演算法（至少圖同構問題就已經是NP問題了），也不知道可以應用在什麼地方。
有什麼指標可以衡量兩個物種間親緣關係的遠近？
綿羊不會飛 分析基因組，發現有很多保守的序列。這些保守的序列，在物種間可以比較。不保守的序列已經面目全非了，沒辦法物種間的比較 所以我們就可以分析物種間的基因序列的相似度了。通過一系列數學計算公式和生物學特點。我們能構建進化樹。樹枝長短代表分歧時間，樹枝分叉點代表，共同祖先。進化樹一畫，所有物種級別...
有兩個或多個鼓手的樂隊有哪些？
asasangrang 乙個敲和太鼓乙個敲爵士鼓算不算 那就是和楽器 和樂器樂團 和太鼓 黑流 旁邊還有彈貝斯的亜沙 爵士鼓 山葵 乙個用身體寫日記的小哥哥 中日混血，中國話東北味那個足的呀 Jintao Xu 路過看到強答一下 我知道兩個鼓的應該有 drew ofthe drew吧https dr...
乙個蛋裡有兩個蛋黃可以吃嗎？
美麗來源健康 就像白生的雙胞胎是雙胞胎一樣，生的雙胞胎都是雙胞胎嗎?當然，刀是沒有害處的。蛋黃多，營養價值高。雙黃雞蛋通常比普通雞蛋大得多。當兩個卵細胞同時成熟，從卵泡中分離並進入輸卵管，在輸卵管中依次被蛋白質 蛋殼和蛋殼包裹，就形成了雙黃。有時會有多個卵子同時成熟並進入輸卵管，形成黃色的卵子。雙黃...