[發明專利]一種基于圖挖掘的社交網絡組隊方法

在審

• 申請號: 201610025181.2
• 申請日: 2016-01-13
• 公開（公告）號: CN105701710A
• 公開（公告）日: 2016-06-22
• 發明（設計）人: 王宇虹;陳志;岳文靜;卜杰;陳雨詩;田思明;黃誠博;劉亞威
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 南京知識律師事務所 32207
• 代理人: 汪旭東

技術領域

本發明涉及一種社交網絡組隊方法，主要利用圖挖掘從全局角度求解最佳組隊方式下的隊員，屬于計算機技術、信息技術、數據挖掘技術交叉技術應用領域。

背景技術

社交網絡，是由社會行動者、二元關系以及人們之間的社會互動組成的社會結構。社交網絡視角提供了一組可用于分析整個社會實體結構的方法，并且提供了一系列理論用以說明從這些結構中觀察到的模式。生活中最常見的也是最直觀的社交網絡，主要包括學術合作、人物關系、在線交友等應用等。

在社交網絡中，個體之間的組隊問題非常普遍。本發明采用最少優先算法，同時采用哈希存儲優化求解過程，尋找最佳的組隊方案。最少優先算法是一種優先處理最少的方法。目前，該算法主要應用在BT系統中文件塊的選擇策略方面，在本發明中，我們應用最少優先算法進行社交網絡中組隊問題的求解。哈希存儲在數據查詢中有著廣泛的應用，是一種力圖將數據元素的存儲哈希位置與關鍵碼之間建立確定對應關系的查找技術。哈希法存儲的基本思想是由節點的關鍵碼值決定節點的存儲地址。本發明將會形成解決全局情況下社交網絡中最佳組隊方案，采用哈希存儲，使問題的解決過程在時間和空間復雜度得到優化，并能求得精確解。本發明給出一種基于圖挖掘的社交網絡組隊方法，該方法將社交網絡中的人員定義為圖模型，依據圖半徑的定義并結合最少優先算法，從全局角度求解社交網絡中的最佳組隊方案，并利用哈希存儲優化求解過程。

發明內容

技術問題：本發明的目的是提供一種基于圖挖掘的社交網絡組隊方法，解決社交網絡中的組隊問題，該問題是指給定一項需要某些技能才能完成的任務，以及具有不同技能的多位候選人，從候選人中選擇部分人進行組隊構成候選人子集，使得該隊的總體技能不但能夠達到完成任務的要求，同時保證該隊中的隊員之間能夠高效地進行交流與工作。

技術方案：所述社交網絡的組隊問題描述如下：設給定一個任務T，該任務的完成需要一些技能，有n個候選人，將候選人集合定義為χ＝{1,2,…,n}，每個候選人個體i都具備技能集X_i。我們假定這些候選人組織在一個帶權無向圖G(χ,E)中，每個候選人看作一個節點，邊的權值定義為候選人之間的交流代價，其中低權值表明兩個候選人之間交流代價更小、更容易進行合作。我們的目標是從候選人集中尋找候選人子集進行組隊，使得最終所組的隊具備能夠完成任務T的能力，而且隊中人員能夠高效地交流與合作。每一個組隊方案是圖G(χ,E)的一個子圖，我們用子圖中的交流代價來描述高效程度，交流代價用直徑R進行表示，即子圖中任意兩節點之間距離的最大值。直徑越小，則表明交流代價越小，該隊的合作和工作效率也越高。

本發明所述的基于圖挖掘的社交網絡組隊方法將社交網絡中的組隊問題定義成圖模型、采用最少優先算法獲得解空間及利用哈希存儲優化求解過程。

本發明所述的基于圖挖掘的社交網絡組隊方法包括以下步驟：

步驟1)根據用戶輸入的信息，構建社交網絡組隊問題的圖模型G，所述圖模型G在建立后，任意兩個候選人之間的最短路都有相應的權值，表示兩者的交流代價；

步驟2)使用最少優先算法，獲得社交網絡組隊問題在圖模型G上的解空間；

步驟3)利用哈希存儲優化求解過程，采用哈希表存儲相關技能集。

其中

所述的步驟1)具體如下：

步驟11)用戶輸入任務完成所需的技能集、候選人集及每個候選人具有的技能集，其中用戶輸入的技能集記為T＝{a₁,a₂,…,a_m}，候選人集記為χ＝{1,2,…,n}；所述m是任務完成需要的技能個數；a_j是第j個技能；n是候選人個數；T表示技能集，也表示所要完成的任務；a_j∈T表示a_j是完成任務T的技能；

步驟12)將所有候選人作為圖模型G中的節點，代表候選人i稱為節點i，所述i∈χ；

步驟13)將候選人i和i′間的路徑看作圖模型G中節點i和節點i′之間的弧，候選人之間的交流代價作為節點i和節點i′之間弧的權值。所述d(i,i′)為圖模型G中節點i到節點i′最短路的權值，且節點間的距離滿足三角不等式，所述i'∈χ；所述三角不等式是指在三角形中，必然有兩邊之和大于第三邊；