作者：王釗? ?編輯：小普
社區(qū)绽昼，即一群擁有相似特征的點须蜗，社區(qū)內(nèi)的點連接緊密目溉，社區(qū)間稀疏連接缭付。
我們可以把同一公司的同事看作是一個社區(qū)內(nèi)的點循未，他們從事同一行業(yè)只厘，可能有相似的教育背景，由于 工作需要河咽，他們之間要進(jìn)行頻繁的溝通赋元。
而不同的公司就像是兩個不同的社區(qū)搁凸，他們之間可能存在著業(yè)務(wù)往來，但關(guān)系遠(yuǎn)沒有公司內(nèi)部連接緊密褥芒。
什么是社區(qū)切分锰扶？
那么發(fā)現(xiàn)這些社區(qū)對我們有什么用呢坷牛？
對于一家需要做廣告宣傳的公司很澄，他一定是想花最少的錢，吸引最多的客戶蹂楣，通過廣告的在某一社群的精準(zhǔn)投放可以達(dá)到這一期望捐迫。
同理施戴，對于銀行信貸業(yè)務(wù)，如何才能降低逾期還款風(fēng)險赞哗，審批時的篩選環(huán)節(jié)非常重要肪笋。
如果一個人所在的社區(qū)大多數(shù)人出現(xiàn)過多次逾期還款記錄，那么這個申請人很有可能就不是一個優(yōu)質(zhì)的客戶猜揪。
社區(qū)是若干社會群體或社會組織聚集在某一個領(lǐng)域里所形成的一個生活上相互關(guān)聯(lián)的大集體而姐，是社會有機體最基本的內(nèi)容划咐，是宏觀社會的縮影。
下面讓我們來一起看看如何進(jìn)行社區(qū)切分：
一種快速迭代社區(qū)劃分方法：Louvain Algorithm
Louvain算法是一種貪婪算法褐缠，運行時間是O(nlogn)队魏，算是非常的快了。
而且類似層級聚類算法俐载，可以提供不同尺度的社區(qū)發(fā)現(xiàn)，這點對于一些定性分析是很有吸引力的挖炬。
Louvain算法分兩個步驟：
1.?對本地節(jié)點轉(zhuǎn)換社區(qū)，并計算Modularity的變化馅巷，從而優(yōu)化網(wǎng)絡(luò)整體的Q钓猬；
2.?把相同社區(qū)的節(jié)點聚合成一個超級節(jié)點敞曹，從而形成一個新的圖。
然后在重復(fù)1局齿，直到最后整個網(wǎng)絡(luò)的Q?不再增加抓歼。
這個算法比較好理解，其中的主要需要解決的就是如何計算第一步中的節(jié)點變換時Q的變化拢锹。
這里就從網(wǎng)絡(luò)最初的原始形式開始谣妻，每個節(jié)點自己就是一個單獨的社區(qū)。
進(jìn)行如下兩步計算：
1.?計算ΔQ?卒稳，這個差距是把節(jié)點i劃歸到它的鄰居節(jié)點j?所在的社區(qū)后Q?的變化值拌禾。
2.?選擇把節(jié)i 劃歸到一個使得ΔQ?最大的鄰居j?所在的社區(qū)。
具體的ΔQ?的計算公式如下：
其中展哭，
對上面這個式子的進(jìn)一步解釋是：
1.?前面大括號里面的部分是把i 加入到社區(qū)C?后的Modularity湃窍。
2.?后面大括號里面的部分是不把i 加入到社區(qū)C?前的Modularity。
與此同時匪傍，需要計算
的值您市，即把節(jié)點i?移除社區(qū)D造成的Modularity的差值役衡。
計算整體的Q的差值：
通過計算這個Modularity的差值，就獲得了一個局部最優(yōu)的社區(qū)集合钉鸯。
則進(jìn)入第二步。
算法的psudo-code見下圖：
上面提到的模塊度是一種衡量社區(qū)劃分的指標(biāo)，可以利用模塊度Modularity Q來衡量社區(qū)劃分的效果捕儒。
模塊度的定義為：
其中，表示節(jié)點i和節(jié)點j的權(quán)重净薛，為所有和節(jié)點i相連的權(quán)重和，m為所有邊權(quán)重之和燃领，是節(jié)點i所屬社區(qū)灵寺，當(dāng)節(jié)點i毁枯，j屬于同一個社區(qū)時，?否則為0赂韵。
模塊度的范圍[-1,1]，當(dāng)模塊度大于0.3-0.7時绍移，社區(qū)劃分效果已經(jīng)很好了恩敌。
模塊度是衡量社區(qū)劃分效果的纠炮，所以希望在社區(qū)內(nèi)部邊的個數(shù)，要遠(yuǎn)大于一個隨機圖中這個社區(qū)內(nèi)部邊的個數(shù)因妇，表達(dá)式上就是：
對于一個隨機圖，它要和真實圖有相同的度分布址芯，對于節(jié)點i和節(jié)點j禀挫，它們的度數(shù)分別是
和
，則節(jié)點i和節(jié)點j期望的邊數(shù)為：?
(其中m為所有邊權(quán)重和）
那么模塊度
等價于上文所提到的模塊度定義。
最后蜜另，有一個很有趣的現(xiàn)象，小普想分享給大家。
通過調(diào)查研究發(fā)現(xiàn)耸序，人們在找工作時罢坝，往往可以通過一般的熟人戈钢，而不是好朋友獲取更多的信息殉了。
弱連接（一般熟人）或許是我們認(rèn)識多元世界的一個很重要的渠道，對于強連接（好朋友）谓娃，往往因為足夠了解俯艰，可以獲得的額外信息并不多。
這樣的發(fā)現(xiàn)也可以啟示我們谓传，多多走出去，認(rèn)識新的人吧~
參考文獻(xiàn)：
http://web.stanford.edu/class/cs224w/slides/04-communities.pdf
https://www.youtube.com/watch?v=pnYwvN8TCio&list=PL1OaWjIc3zJ4xhom40qFY5jkZfyO5EDOZ&index=3
https://blog.csdn.net/infovisthinker/article/details/104724677
https://zhuanlan.zhihu.com/p/138824980
- 完 -
想了解更多關(guān)于人工智能的資訊
歡迎關(guān)注公眾號：普適極客
