[發明專利]一種基于通信網的重要用戶發現及行為預測方法

有效

• 申請號: 202110541915.3
• 申請日: 2021-05-18
• 公開（公告）號: CN113395172B
• 公開（公告）日: 2022-11-11
• 發明（設計）人: 李艷斌;李淳;劉嶠;李銀強;代婷婷;周樂;宋明慧;曾義夫;孫建強;曾維智;藍天;吳祖峰
• 申請（專利權）人: 中國電子科技集團公司第五十四研究所;電子科技大學
• 主分類號: H04L41/147
• 分類號: H04L41/147;H04L41/142
• 代理公司: 成都東恒知盛知識產權代理事務所(特殊普通合伙) 51304
• 代理人: 羅江

1.一種基于通信網的重要用戶發現及行為預測方法，其特征在于：包括以下步驟：

步驟1、依據用戶通信記錄，構建出用戶的通信網絡，利用基于社區劃分的關鍵節點查找方法，查找網絡中的重要節點，挖掘出重要用戶；

步驟2、依據用戶通信記錄，提取出用戶通信時間的特征，構建折線圖，挖掘出全局通信時間的規律；

步驟3、依據用戶通信記錄，構建用戶的歷史通信對象序列，對于挖掘出的重要用戶，利用NARM模型，預測出用戶下一刻通信對象；

步驟4、基于以上3步的輸出結果，篩選出未來時間中重要用戶的通信時間和通信對象的預測結果，從而得出重要用戶及行為趨勢的預測結果；

步驟1中使用基于平衡樹的Fast-Newman算法對網絡進行社區劃分，然后再對每個社區，單獨利用PageRank算法進行關鍵點查找，最后綜合社區劃分和PageRank算法得出每個節點的重要性，具體過程包括如下步驟：

步驟1-1：根據某個時間段內用戶通信記錄下的主叫用戶和被叫用戶信息，提取出該時間段內的所有用戶集合及用戶集合個數；

步驟1-2：在步驟1-1的基礎上，以用戶集合中的每個用戶作為用戶通信網絡中的節點，并根據用戶通信記錄中的主叫號碼、被叫號碼、主叫、被叫信息，建立通信網絡中的節點間通信的邊，其中用戶通信網絡為無向圖G(V，E)；在G(V，E)中允許兩個節點間存在多條邊；

步驟1-3：依據用戶通信網絡的拓撲結構，利用Fast-Newman算法對網絡進行社區劃分，首先初始化每個節點為一個社區，網絡一共N個節點則共有N個社區；模塊度Q＝0，初始化e_uv：

如果節點u和v之間有連邊：其中m為無向圖總的邊數，其中tot為節點u和v之間的邊的數量；

如果節點u和v之間沒有連邊：e_uv＝0；

并且a_u滿足：

a_u＝k_u/2m；其中k_u表示與節點u相連的邊的數量；

把網絡中的每一條無向邊，拆分成兩條有向邊，e_uv表示節點u與節點v相連的邊的數量占整個網絡的比例，a_u表示與節點u相連的邊占整個網絡的比例；

步驟1-4：對于有邊聯系的兩個節點u和v比作兩個社區，將兩個節點合并為一個新的節點即形成一個新的社區，并根據下式計算合并后模塊度的增量：

ΔQ＝e_uv+e_vu-2a_ua_v＝2(e_uv-a_ua_v)；

根據Fast-Newman算法的原理，需要找到模塊度Q最大時對應的網絡節點合并情況，因此采用貪心原理，每次選擇產生最大ΔQ的兩個節點進行合并，并且記錄下每次合并的節點；對于每兩個有邊聯系的兩個節點新建一條邊，并將邊權設置為2(e_uv-a_ua_v)，并且將這些邊按照邊權的大小插入平衡樹中；

步驟1-5：開始合并兩個節點，根據平衡樹的性質容易得到最大的邊權的邊，將邊權最大的邊的兩個端點的節點u和v進行合并同時將邊從平衡樹中進行刪除，并記錄下合并記錄，合并后的新的聚合節點為z，那么新節點的屬性如下：

e_zz＝e_uu+e_vv+e_uv+e_vu；

e_zx＝e_ux+e_vx；

a_z＝a_u+a_v；

其中x為除z，u，v之外的并且與u和v相連的節點，把網絡中的每一條無向邊，拆分成兩條有向邊，則e_zz表示合成的節點z中的邊數占原始整個無向圖中的比例；

根據步驟1-4計算模塊度的增量，將合并前的與u和v相連的邊并且在平衡樹中的邊進行刪除，然后根據新合并的節點z的屬性重新設置新的邊及計算新的邊權，再插入到平衡樹中；

步驟1-6：重復步驟1-5的操作N-1次，這時就只剩下一個合并后的新節點，然后根據最大的Q值所對應的節點合并步驟，將整個圖的n個點當作n個單獨的聯通塊，使用并查集模擬這個過程，把最終每一個聯通塊看成一個社區，即可得到最大的Q值對應的社區劃分；

步驟1-7：根據社區劃分的結果圖G(V，E)被劃分為G₁,G₂,...,G_k，其中k為社區數量，子圖G_i(V_i,E_i)表示一個社區，其中V_i表示社區內的節點，E_i表示社區的內部關系并且E_i兩個端點都在子圖G_i內，并且V₁∪V₂∪...∪V_k＝V；將G_i聚合成一個超級節點s_i，構建超級節點的鄰接矩陣S，S的元素S_ij表示社區i和j之間的連邊的權重之和，由于無向圖G為非帶權圖，所以鄰接矩陣的連邊的權重便是兩個社區的連邊總數：

S_ij＝T_ij；

T_ij為社區i和社區j的連邊總數，當i＝j時為同一個社區，此時T_ij為社區內部邊的數量的兩倍；

步驟1-8：求取各節點在各自社區內的PageRank值，利用PageRank算法對每個子圖的每一個節點計算其PageRank值：

其中，y表示與x在同一社區的節點，如果y和x直接相連，則σ(x,y)值為1,否則為0，k_y表示y節點在子圖G_i內的出度，PR’(x)為x在上一時間段所在社區的PageRank值，初始為零；對于不同社區，采用多路計算的方式，分攤到多個線程進行計算；

步驟1-9：定義一個衡量社區內部連結關系和外部連結關系的數值，社區i的連結系數；定義為社區的內部度即與外界相連的邊，為社區的外部度即社區內部的邊，則根據S矩陣可得：

定義社區i的連結系數為I_i，采用如下公式進行計算：

接下來對社區連結系數進行歸一化處理，使用softmax函數進行歸一化；

其中是社區x被選擇的概率，k為社區數量；

步驟1-10：計算每個節點重要程度；將每一個節點利用綜合公式計算Rank值在進行排序，對于節點x的Rank值計算如下：

其中G_x為x所在的社區，|G_x|為x所在社區的大小；通過計算，將所有的節點的Rank值進行排序，可以得到整個網絡的節點的重要性排序，選取Rank值最大的節點或者前幾個節點，就可以挖掘出網絡中的一個或多個重要用戶。