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

在審

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

1.一種基于圖挖掘的社交網絡組隊方法，其特征在于該方法包括以下步驟：

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

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

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

2.根據權利要求1所述的一種基于圖挖掘的社交網絡組隊方法，其特征在于所述的步驟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'∈χ；所述三角不等式是指在三角形中，必然有兩邊之和大于第三邊；

步驟14)用X_i表示候選人i所代表的節點所具備的技能集，當a_j∈X_i時，候選人i具有技能a_j；當時，候選人i不具有技能a_j；

步驟15)定義候選人子集當χ'中至少有一個候選人具有技能a_j時，χ'有技能a_j，定義χ'的覆蓋為C(χ′,T)。所述C(χ′,T)表示χ'完成任務T必需的技能并且在χ'中每個候選人至少具備T中一種技能，即C(χ′,T)＝T∩(∪_i∈χ′X_i)，用Path(i,i′)表示節點i到節點i′的最短路上的節點集，定義d(i,χ′)＝min_i′∈χ′d(i,i′)，表示節點i到候選人子集χ′的最短距離，其中i∈χ且定義Path(i,χ′)表示從i到k＝argmin_i′∈χ′d(i,i′)最短路上的節點集，所述k＝argmin_i′∈χ′d(i,i′)是i到χ'所構成子圖上最短路的終點。