??k-Core算法是一種用來在圖中找出符合指定核心度的緊密關聯(lián)的子圖結構桑孩，在k-Core的結果子圖中，每個頂點至少具有k的度數(shù)，且所有頂點都至少與該子圖中的 k 個其他節(jié)點相連衙伶。k-Core通常用來對一個圖進行子圖劃分蕴潦，通過去除不重要的頂點，將符合逾期的子圖暴露出來進行進一步分析汪榔。k-Core由于其線性的時間復雜度和符合直觀認識的可解釋性蒲拉，在風控金融，社交網絡和生物學上都具有較多的應用場景痴腌。目前在Networkx中已經提供了各種k-core相關的算法實現(xiàn)雌团，有需要的可以參考Networkx入門指南——圖分析之k-core.
算法原理
??k-Core算法是一種子圖挖掘算法，用于尋找一個圖中符合指定核心度的頂點的集合衷掷，即要求每個頂點至少與該子圖中的其他k個頂點相關聯(lián)辱姨。如圖1所示，分別對應1-Core戚嗅，2-Core和3-Core雨涛，任何一個圖，在不包含孤立頂點的情況下懦胞，都是1-Core的替久。
圖 1
??k-Core算法的過程也是非常簡單的，一共分為兩步躏尉，其實兩步所做的內容是一樣的蚯根，至于為什么要分兩步執(zhí)行同一個過程，可以自行思考一下胀糜。
Input：圖G颅拦，核心度k
Step 1：將圖G中度數(shù)小于k的頂點全部移除，得到子圖G'教藻。
Step 2：將圖G'中度數(shù)小于k的頂點全部移除距帅，得到新子圖G''。該子圖G''就是最終k-Core劃分的結果子圖括堤。
??圖2中我們給出了一個簡單的3-Core子圖劃分的過程碌秸。
圖2. 求解3-Core的過程
算法應用
??k-core算法通常用來找出一個圖中符合指定k核心度的子圖绍移，該子圖在圖中承擔著核心的地位，核心度越高讥电，子圖越小蹂窖，該子圖對應的核心度也越大。從某種意義上來說核心度劃分的子圖在原圖中承擔著比較重要的角色恩敌，如圖的起源和演化趨勢追溯瞬测，圖中介識別等。具體的應用場景有很多潮剪，大家可以參考一篇論文：k-core: Theories and applications涣楷。
