Martin Rosvall等人基於資訊理論提出了Infomap算法。該算法使用隨機遊走作為網路上信息傳播的代理，網路上的隨機遊走會產生相應的數據流。隨機遊走產生的信息量使用平均一步隨機遊走產生的碼字長度衡量，即平均碼字長度。為了最大的壓縮平均碼字長度，需要開發有效的編碼方法。霍夫曼編碼是一種常用的編碼方式，在示例圖上使用該編碼，分配較短的碼字給隨機遊走經常訪問的節點，香濃信源編碼理論給出了霍夫曼編碼碼字長度的理論界限：每一步的平均碼字長度不低於變數X的熵。其中，變數X的樣本空間是網路所有節點的集合，X的機率分布為網路所有節點被隨機遊走訪問的頻率分布。由於霍夫曼編碼沒有利用網路結構的規律性，所以該平均碼字長度仍然比較長。為了進一步壓縮信息流的編碼長度，可以考慮使用突出網路社區結構的二級編碼。
這個規則類似於地圖上的命名規則，社區類似於城市，節點類似於城市裡的街道，不同的城市裡的街道可以同名，同一個城市裡的街道不能同名。將隨機遊走訪問社區或者節點的頻率分布作為變數的機率分布，社區的碼字和每個社區內部節點的碼字都使用霍夫曼編碼。每次隨機遊走跨越不同的社區時，需要在描述中加上前一個社區的離開碼和後一個社區的碼字，以表示隨機遊走所處的社區發生了變化。直觀上看，如果社區的劃分較好，則隨機遊走者在某個社區內部遊走的機率將較大，跨越社區的機率將較小，因此使用社區編碼和離開碼的機率將較小，同時由於兩級編碼降低了每個節點的碼字長度，因此信息流的平均碼字長度將會被壓縮。二級編碼方法將網路的社區劃分問題轉化成了最優編碼問題：尋找網路的一個最優劃分，使無限隨機遊走的平均描述長度最小。這裡，描述長度包括兩個部分：隨機遊走者在社區內部遊走時節點的碼字長度和跨越社區時社區的碼字長度。顯然，如果社區劃分較好，那么隨機遊走在社區間的轉移頻率就比較低，從而使描述中社區的平均碼字長度較低，同時，節點的碼字長度因為二級編碼被大大降低，因此總的描述長度就會被大大的壓縮。相反，如果社區沒有被很好的劃分，社區間的轉移將會很頻繁，從而二級編碼將不能壓縮隨機遊走的描述長度。
假設給定網路的一個社區劃分M，將網路的n個節點劃分到m個社區中，則網路上無限隨機遊走每一步的平均描述長度L（M）為：
H(Q)+pH(P)
稱為map等式。其中，第一項q H（Q）表示在社區間轉移所需要的平均碼字長度，第二項H（P）表示在所有社區內遊走的平均碼字長度。網路社區發現的目標就是在所有可能的社區劃分中，找出使平均描述長度L（M）最小的劃分作為網路最優的社區劃分。
採用貪心算法尋找最優劃分，即開始時為每個節點分配一個獨立的社區，合併使平均描述長度L（M）下降最多的兩個社區，重複這個過程，直到最後合併成一個社區。算法的具體的步驟如下所述：
（1）去掉網路中所有的邊，網路的每個節點都單獨作為一個社區；
（2）網路中的每個連通部分作為一個社區，將還未加入網路的邊分別重新加回網路，如果加入網路的邊連線了兩個不同的社區，即合併了兩個社區，則計算形成的新的社區劃分的平均描述長度的減少量。選擇使平均描述長度減少最大的兩個社區進行合併；
（3）如果網路的社區數大於1，則返回步驟 （2） 繼續疊代，否則轉到步驟 （4） ；
（4）遍歷每種社區劃分對應的平均描述長度的值，選取平均描述長度最小的社區劃分作為網路的最優劃分。
