一、前言
在論文「Real-time Event Detection on Social Data Streams」中，作者首先在每一個時間窗口（分鐘級）內利用社區發現算法（Louvain method）得到一個聚類
We filter out any edges whose weight falls below a threshold and perform maximum weighted bipartite matching to find cluster links.
論文將節點之前的權重定義為：
The edge weight between them is a measure of how many entities these clusters share, similar to the cosine similarity described earlier.
背景交代完，接下來我們就開始補充二分圖匹配問題、匈牙利算法和KM算法的相關知識。
二、二分圖匹配問題
所謂二分圖（Bipartite Graph）就是這樣一個圖：
簡單地說，就是一張圖裡的所有點可以分為兩組（如上圖），並且每條邊都跨越兩組。這樣的圖就是二分圖。
1. 二分圖的定義
說的嚴謹一點：
二分圖又稱雙分圖、二部圖、偶圖，指頂點可以分成兩個不相交的集U和V（U和V皆為獨立集（Independent Sets）），使得在同一個集內的頂點不相鄰（沒有共同邊）的圖。
一個圖為二分圖僅當：
2. 相關的幾個概念
我們定義匹配點、匹配邊、未匹配點、非匹配邊。如圖3,1、4、5、7為匹配點，其他頂點為未匹配點；1-5、4-7為匹配邊、其他邊為非匹配邊。
匹配（matching）：二分圖的一個「匹配」是指一些邊的集合，任意兩條邊沒有公共點。例如，圖3、圖4中紅色的邊就是圖2的匹配。
最大匹配（maximum matching）：二分圖的「最大匹配」，值的是二分圖的所有匹配中邊數最多的匹配。圖4是一個最大匹配。它包含4條匹配邊。
完美匹配（perfect matching）：二分圖的一個「完美匹配」，是指所有點都在這個匹配中的一個匹配。也就是說這個匹配裡的所有邊剛好經過所有點一次。圖4是一個完美匹配，顯然，完美匹配一定是最大匹配（完美匹配的任何一個點都已經匹配，添加一條新的匹配邊一定會與已有的匹配邊衝突）。但並非每個圖都存在完美匹配。
舉例來說：如下圖所示，如果在某一對男孩和女孩之前存在相連的邊，就意味著他們彼此喜歡。是否可能讓所有男孩和女孩兩兩配對，使得每對都互相喜歡？圖論中，這就是完美匹配問題。如果換一個說法：最多有多少對互相喜歡的男孩/女孩可以配對？這就是最大匹配問題。
下面先講匈牙利算法（Hungarian Algorithm），匈牙利算法用於求解無權二分圖（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching）。
三、匈牙利算法
匈牙利算法是一種在多項式時間內求解任務分配問題的組合優化算法，並推動了後來的原始對偶方法。美國數學家哈羅德·庫恩於1955年提出該算法。此算法之所以被稱作匈牙利算法，是因為算法很大一部分是基於以前匈牙利數學家 Dénes Kőnig 和 Jenő Egerváry 的工作之上創建起來的。詹姆士·芒克勒斯在 1957 年回顧了該算法，並發現（強）多項式時間的。此後該算法被稱為 Kuhn–Munkres 算法或 Munkres 分配算法。原始算法的時間複雜度為
這段文字為我們講述匈牙利算法的歷史姻緣……
1. 相關的幾個概念和定理
在講匈牙利算法之前，先學習幾個概念，這些概念都是為匈牙利算法服務的。
交替路：從一個未匹配點出發，依次經過非匹配邊、匹配邊、非匹配邊…形成的路徑叫交替路。
增廣路：從一個未匹配點出發，走交替路，如果以另一個未匹配點（出發的點不算）為結尾，則這條交替路稱為增廣路（agumenting path）。例如，圖 5 中的一條增廣路如圖 6 所示（圖中的匹配點均用紅色標出）：
增廣路有一個重要特點：非匹配邊比匹配邊多一條。因此，研究增廣路的意義是改進匹配。只要把增廣路中的匹配邊和非匹配邊的身份交換即可。由於中間的匹配節點不存在其他相連的匹配邊，所以這樣做不會破壞匹配的性質。交換後，圖中的匹配邊數目比原來多了 1 條。
我們可以通過不停地找增廣路來增加匹配中的匹配邊和匹配點。找不到增廣路時，達到最大匹配（這是增廣路定理）。匈牙利算法正是這麼做的。
增廣路定理：任意一個非最大匹配的匹配一定存在增廣路。
匈牙利樹一般由BFS構造（類似於BFS樹）。從一個未匹配點出發運行BFS（唯一的限制是，必須走交替路），直到不能再擴展為止。例如，由圖7，可以得到如圖8的一棵 BFS 樹：
這棵樹存在一個葉子節點為非匹配點（7 號），但是匈牙利樹要求所有葉子節點均為匹配點，因此這不是一棵匈牙利樹。如果原圖中根本不含 7 號節點，那麼從 2 號節點出發就會得到一棵匈牙利樹。這種情況如圖 9 所示（順便說一句，圖 8 中根節點 2 到非匹配葉子節點 7 顯然是一條增廣路，沿這條增廣路擴充後將得到一個完美匹配）。
2. 算法基本原理
注意前面增廣路的定義：「從一個未匹配點出發，走交替路，以另一個未匹配點為結尾」，首尾都是未匹配點，說明首尾的邊都是非匹配邊。而又是交替路，也就是說非匹配邊比匹配邊多一條。那麼我們完全可以把這條增廣路裡的匹配邊和非匹配邊互換（稱為「交換匹配」），那麼匹配邊就會多出 1 條，實現了「增廣」的意義。並且這樣做並不會對其他邊造成影響，也不破壞二分圖的性質。
那麼我們就可以一直找增廣路，不斷交換匹配。根據增廣路定理，如果找不到了，就說明已經達到最大匹配。
同樣可以證明，已經匹配的點永遠不會退出匹配，只會更換匹配。
這就是匈牙利算法最核心的部分了：一直找增廣路，不斷交換匹配。
可能看完上面的敘述，還是有點困惑。一直找增廣路，不斷交換匹配到底應該怎麼做？以下我舉一個便於理解例子：
現在Boys和Girls分別是兩個點集，裡面的點分別是男生和女生，邊表示他們之間存在「曖昧關係」。最大匹配問題相當於，假如你是紅娘，可以撮合任何一對有曖昧關係的男女，那麼你最多能成全多少對情侶？（數學表述：在二分圖中最多能找到多少條沒有公共端點的邊）
現在我們來看看匈牙利算法是怎麼運作的：
我們從B1看起（男女平等，從女生這邊看起也是可以的），他與G2有曖昧，那我們就先暫時把他與G2連接（注意這時只是你作為一個紅娘在紙上構想，你沒有真正行動，此時的安排都是暫時的）。
來看B2，B2也喜歡G2，這時G2已經「名花有主」了（雖然只是我們設想的），那怎麼辦呢？我們倒回去看G2目前被安排的男友，是B1，B1有沒有別的選項呢？有，G4，G4還沒有被安排，那我們就給B1安排上G4。
我們來細看這一過程：
這是不是正是前面提到的一直找增廣路，不斷交換匹配。
我們繼續，B3直接配上G1就好了，這沒什麼問題。至於B4，他只鍾情於G4，G4目前配的是B1。B1除了G4還可以選G2，但是呢，如果B1選了G2，G2的原配B2就沒得選了。我們繞了一大圈，發現B4隻能註定單身了，可憐。（其實從來沒被考慮過的G3更可憐）
匈牙利算法的要點如下：
1）從左邊第1個頂點開始，挑選未匹配點進行搜索，尋找增廣路。
2）由於找到增廣路之後需要沿著路徑更新匹配，所以我們需要一個結構來記錄路徑上的點。DFS版本通過函數隱式地使用一個棧，而BFS版本使用一個隊列。
3. 匈牙利算法的應用
這一部分其實與所要敘述的目標相關性不大，不過開闊開闊思路總是好的。
一些題目，乍一看與上面這個男女配對的問題沒有任何相似點，其實都可以用匈牙利算法。例如：
（洛谷P1129） [ZJOI2007]矩陣遊戲
題目描述
小Q是一個非常聰明的孩子，除了西洋棋，他還很喜歡玩一個電腦益智遊戲――矩陣遊戲。矩陣遊戲在一個
每次可以對該矩陣進行兩種操作：
行交換操作：選擇矩陣的任意兩行，交換這兩行（即交換對應格子的顏色）
列交換操作：選擇矩陣的任意兩列，交換這兩列（即交換對應格子的顏色）
遊戲的目標，即通過若干次操作，使得方陣的主對角線(左上角到右下角的連線)上的格子均為黑色。
對於某些關卡，小Q百思不得其解，以致他開始懷疑這些關卡是不是根本就是無解的！於是小Q決定寫一個程序來判斷這些關卡是否有解。
輸入格式
第一行包含一個整數T，表示數據的組數。
接下來包含T組數據，每組數據第一行為一個整數N，表示方陣的大小；
接下來N行為一個
輸出格式
包含T行。對於每一組數據，如果該關卡有解，輸出一行Yes；否則輸出一行No。
我們把矩陣轉化為二分圖（左側集合代表各行，右側集合代表各列，某位置為1則該行和該列之間有邊）。我們想進行一系列交換操作，使得X1連上Y1，X2連上Y2，……
大家可以想像，所謂的交換，是不是可以等價為重命名？我們可以在保持當前二分圖結構不變的情況下，把右側點的編號進行改變，這與交換的效果是一樣的。
所以想讓X1、X2...與Y1、Y2...一一對應，其實只需要原圖最大匹配數為4就行了。（這與組合數學中相異代表系的概念相合）。實現代碼及更多應用參見[1]
四、KM（Kuhn-Munkres）算法
好，前菜和頭盤都上完了，現在我們來吃主菜，祝你有個好胃口！
1. 相關的幾個概念和定理
完備匹配：定義 設G＝<V1，V2，E>為二部圖，|V1|≤|V2|，M為G中一個最大匹配，且|M|＝|V1|，則稱M為V1到V2的完備匹配。也就是說把一個集合中的點全部匹配到另一個集合中。在上述定義中，若|V2|＝|V1|，則完備匹配即為完美匹配，若|V1|<|V2|，則完備匹配為G中最大匹配。
二分圖最優匹配：對於二分圖的每條邊都有一個權（非負），要求一種完備匹配方案，使得所有匹配邊的權和最大，記做最優完備匹配。（特殊的，當所有邊的權為1時，就是最大完備匹配問題）
二分圖帶權匹配與最優匹配：什麼是二分圖的帶權匹配？二分圖的帶權匹配就是求出一個匹配集合，使得集合中邊的權值之和最大或最小，這個匹配集合比一定是完備匹配。而二分圖的最優匹配則一定為完備匹配，在此基礎上，才要求匹配的邊權值之和最大或最小。二分圖的帶權匹配與最優匹配不等價，也不互相包含。
頂標：每個節點與另一個集合中節點之間的最大權值
可行頂標（標杆）：對於原圖中的任意一個結點，給定一個函數
相等子圖：設 G(V,E) 為二部圖， G'(V,E') 為二部圖的子圖。如果對於 G' 中的任何邊<x,y> 滿足，
以下是一些擴展的內容：
KM算法是求最大權完備匹配，如果要求最小權完備匹配怎麼辦？
方法很簡單，只需將所有的邊權值取其相反數，求最大權完備匹配，匹配的值再取相反數即可。
KM算法的運行要求是必須存在一個完備匹配，如果求一個最大權匹配(不一定完備)該如何辦？
依然很簡單，把不存在的邊權值賦為0。
KM算法求得的最大權匹配是邊權值和最大，如果我想要邊權之積最大，又怎樣轉化？
還是不難辦到，每條邊權取自然對數，然後求最大和權匹配，求得的結果a再算出e^a就是最大積匹配。至於精度問題則沒有更好的辦法了。
2. 算法流程
這裡有一篇比較好的男女找對象指南博客講解了KM算法的執行過程，生動而又形象。主要理解過程中是怎麼滿足配對條件的，不滿足後怎麼辦，過程中降低期望值d是怎麼求得的，在配對失敗期望值進行更改以後發生了那些變化，這些變化為新的一輪的匹配帶來了什麼？[2]
3. 算法原理
算法原理在[3]做了很好解釋（好吧，是我寫累了，還要去跑步），可以移步學習。
以上是KM算法的基本思想。但是樸素的實現方法，時間複雜度為
以上就是全部內容，關於代碼我會實現python版本的，在論文「Real-time Event Detection on Social Data Streams」論文筆記完成並復現完成後給出github地址，完結撒花。
引用：
[1] https://zhuanlan.zhihu.com/p/96229700
[2] https://www.cnblogs.com/wenruo/p/5264235.html
[3] https://blog.csdn.net/x_y_q_/article/details/51927054