[發明專利]一種網絡特征社區查找方法

有效

• 申請號: 202010075210.2
• 申請日: 2020-01-22
• 公開（公告）號: CN111274498B
• 公開（公告）日: 2023-06-23
• 發明（設計）人: 王宏志;王春楠;陳含笑
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 張利明

1.一種網絡特征社區查找方法，其特征在于，該方法的具體步驟為：

步驟一、根據真實的社區的內部結構特征，建立社區節點的內部連結密度評估函數；

步驟二、根據真實的社區的外部結構特征，建立社區節點的外部連結密度評估函數；

步驟三、對待搜索的網絡社區的屬性和給定屬性之間的相關度進行量化，建立網絡社區的屬性相關性評估函數；

步驟四、對社區節點的內部連結密度評估函數、社區節點的外部連結密度評估函數和量化的待搜索的網絡社區的屬性和給定屬性相關度的函數進行融合，獲取函數RACSF(S，Wq)；其中，S是G(V，E)中的一組節點，G(V，E)是一個無向圖，Wq為特征屬性集合；

獲取RACSF(S，Wq)函數為：

其中，RACSF(S，Wq)表示的是當目標屬性集合為W_q時節點集S的RACSF值；所述RACSF的值用于評估搜索到的節點集S的質量；AttriScore(S，W_q)為待搜索社區的特征屬性集合Wq和節點集之間相關度函數，Nodes(S，w)＝{v：v∈S，w∈attr(v)}，Nodes(S，w)為S中所有覆蓋屬性w的節點的集合，所述屬性w屬于搜索社區的特征屬性集合Wq，ns為節點集合S中節點的個數，n_S＝|S|；D(u)是節點u的度，D(u)＝|(u，v)∈E|，Average-ODF(S)為外部連結密度評估函數，Inner(S)為構建的內部連結密度評估函數；v為圖G(V，E)中的一個節點，m_S為節點集合S中邊的個數，m_S＝|(u，v)∈E：u∈S，v∈S|，d(v，S)為節點v在節點集合S中的內部連接邊數，d(v，S)＝|(u，v)∈E：u∈S|；d²(v，S)是d(v，S)的2次方；

步驟五、利用NSS節點選擇策略和彈性ISC循環終止條件對RACSF(S，Wq)函數進行優化，獲取目標社區結構的最優解為最終查找的特征社區；

所述利用NSS節點選擇策略和彈性ISC循環終止條件對RACSF(S，Wq)函數進行優化，獲取目標社區結構的最優解為最終查找的特征社區的具體方法為：

當循環滿足條件：

中任意一個則停止后續循環，并將循環停止后的OptimalGroup(t)作為目標社區結構的最優解；其中，DeRatioL和ConDeNumL為常數，DecreaseRatio(t)為Score(t)和OptimalScore(t)之間的比值，OptimalScore(t)為在加入由NSS節點選擇策略推薦的第t個節點之前，節點集合獲得的最大RACSF評分，Score(t_i)為節點集合Group(t_i)的RACSF評分，Score(t)為節點集合Group(t)的RACSF評分，Group(t_i)為使用NSS節點選擇策略加入t_i個節點后獲得的社區結構；Group(t)為使用NSS節點選擇策略加入t個節點后獲得的社區結構；min{argmax_ti＜tScore(t_i)}表示節點集合取得當前最大RACSF評分時，使用NSS節點選擇策略加入的最少節點個數。

2.根據權利要求1所述一種網絡特征社區查找方法，其特征在于，步驟一所述的建立社區節點的內部連結密度評估函數的具體方法為：

利用DensityB(S)函數：

構建內部連結密度評估函數Inner(S)：

其中，DensityB(S)的范圍為[0，n_s-1]AvgDeg(S)是節點集合S的平均度。

3.根據權利要求2所述一種網絡特征社區查找方法，其特征在于，步驟二中所述建立社區節點的外部連結密度評估函數的具體為：

外部連結密度評估函數Average-ODF(S)：

4.根據權利要求3所述一種網絡特征社區查找方法，其特征在于，步驟三所述對待搜索的網絡社區的屬性和給定屬性之間的相關度進行量化的具體方法為：

利用公式：

對所給特征屬性集合Wq與節點組S之間的相關度(S，Wq)進行量化。