[發明專利]一種基于地理位置的網絡重構方法

有效

• 申請號: 201710520291.0
• 申請日: 2017-06-30
• 公開（公告）號: CN107357858B
• 公開（公告）日: 2020-09-08
• 發明（設計）人: 鄭子彬;李友
• 申請（專利權）人: 中山大學
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06Q50/00
• 代理公司: 廣東廣信君達律師事務所 44329
• 代理人: 楊曉松

本發明涉及一種基于地理位置的網絡重構方法，包括以下步驟：S1、計算節點網絡結構相似度；S2、計算用戶地理位置相似度；S3、結合節點網絡結構相似度和用戶地理位置相似度，建立統一的相似度；S4、采用閾值處理的方法，對步驟S3得到的統一的相似度進行過濾，根據過濾結果重新構建一個有權網絡。本發明結合用戶地理位置這一動態特征對社交網絡進行重構，重構后的網絡圖更容易獲得有位置特征的網絡特性；基于有權值的網絡結構進行社區發現的結果具有地理位置信息的社區劃分；構造后進行社區發現，可以得到在地理位置上面分布比較集中的社區。

技術領域

本發明涉及網絡優化的技術領域，尤其涉及到一種基于地理位置的網絡重構方法。

背景技術

生活中存在著各種各樣的網絡，如科研合作網絡、演員合作網絡、城市交通網絡、電力網、以及像QQ、微博、微信這樣的社交網絡。社交網絡的核心是參與其中的用戶以及用戶之間的關系。一般采用圖模型來為其進行建模，其中的節點表示社交網絡中用戶，連邊則表示用戶與用戶之間的關系，關系的緊密程度通過連邊上的權重進行區分，權重越大，關系距離越小，關系強度越大，關系越親密。

基于社交網絡的建模，可以得到圖結構，在圖中包含著一定的結構，其中存在一個一個的節點子集合，在這些子集合的內部存在較多的邊，而子集合與子集合之間存在較少的邊。這種子結構就被稱為社區，社區發現算法就是通過對網絡結構的理解，構造算法去發現識別出社區，從而進行進一步地應用來實現好友推薦、節點屬性識別等場景。

社區發現是一件很有意義的事情。在算法層面上來說，屬于無監督的圖聚類算法，所以具備聚類算法所能達到的效果，對一個大型網絡調用社區發現算法，其實是對其按照特定標準進行了劃分，在此基礎上可對每個社區做進一步的發掘。而從計算的角度而言，社區分劃相當于分解了任務，起到了降低計算復雜度的作用。

移動互聯網時代的到來，促進社交網絡的飛速發展，社交網絡中的信息越來越豐富，傳統社交網絡的研究是單純基于用戶與用戶之間的好友關系，通過好友關系建立一個網絡圖，在網絡圖中，節點代表用戶，連邊表示用戶之間以某種方式產生連接，比如在朋友圈內互為好友，或者同在一個興趣群內等。

然而，社交網絡中的信息除了相對而言比較靜態的好友關系鏈以外，還存在更多用戶本身的屬性，網絡圖中的節點各不相同，每個都有各自的其他屬性來描述這個個體。可見，傳統社交網絡不利于社交網絡的分析，特別是社區發現這方面。

發明內容

本發明的目的在于克服現有技術的不足，提供一種重構后的網絡更容易獲得有位置特征的網絡特性、進行社區發現的結果具有地理位置信息的社區劃分、社區發現能得到在地理位置上面分布比較集中的社區的基于地理位置的網絡重構方法。

為實現上述目的，本發明所提供的技術方案如下：

關于節點網絡結構相似度：

在社交網絡中用戶與用戶之間因為某種關聯而以連邊的形式在網絡圖中表示，比如用戶A和用戶B在社交媒體上互為好友關系，那么就可以說在網絡圖中節點A和節點B有一條連邊。

根據不同的規則，可以構造出有權網絡圖和無權網絡圖，在無權圖中用戶與用戶之間的連邊沒有權重，也即每條連邊權重一樣。在有權圖中，根據相應規則確定權重，比如用戶A和用戶B在社交媒體上的交互次數比較少，那么節點A、B之間的連邊就可以賦一個較小的權重，如0.4，用戶A和用戶C交互比較多，那么節點A、C之間就賦一個較大的權值。在網絡圖中，相互之間有連邊的兩個節點互為鄰居。

構建網絡之前，需要定義網絡中兩個節點的相似度，從物理意義上來講，衡量兩個節點的相似度，根據他們的鄰居節點來表示，也就是說，兩個節點之間若有較多共同鄰居，則在網絡圖結構上存在較大相似性。本方案采用Jaccard相似度方法計算網絡中任意兩個節點之間的相似度。

在無權圖中，節點u，v的Jaccard相似度表示為：