[發明專利]用于局部和平衡的動態映射的系統和方法

有效

• 申請號: 201380080013.8
• 申請日: 2013-11-20
• 公開（公告）號: CN105593838B
• 公開（公告）日: 2019-09-03
• 發明（設計）人: 亞歷山德羅·普雷斯塔;阿隆·邁克爾·沙利塔
• 申請（專利權）人: 臉譜公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06Q10/10;G06Q50/00
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 梁麗超;劉彬

對于局部和平衡動態映射節點，在實施方式中，計算機實現方法、系統和計算機可讀介質可以計算第一分區中的節點的柱狀圖。可以計算第二分區中的節點的柱狀圖。基于第一分區中的節點的柱狀圖，第二分區可以被選擇為第一分區中的節點組的候選分區。基于第二分區中的節點的柱狀圖，第一分區可以被選擇為第二分區中的節點組的候選分區。基于負載平衡，第一分區中的節點組的至少一部分可以被映射至第二分區，并且第二分區中的節點組的至少一部分可以被映射至第一分區。

技術領域

本發明涉及節點圖譜領域，具體地涉及計算機實現方法和系統以及存儲介質。更具體地，本發明提供用于將節點映射至分區的技術。

背景技術

社交網絡網站提供各個成員在其中可連接至其他成員并與其他成員通信的動態環境。這些網站通常可提供在線機構，從而允許各個成員在其先前存在的社交網絡中交互，以及創建新的社交網絡。成員可包括任何個體或者實體，諸如，組織或者企業。在其他屬性中，社交網絡網站允許成員將相關信息有效并且高效地傳送至他們的社交網絡。

社交網絡的成員可以將信息、新聞報道、關系活動、音樂、視頻以及任何其他感興趣的內容突出顯示或分享至專用于該成員的或者另外對這樣的內容可用的網站的區域。社交網絡的其他成員可以通過瀏覽成員簡檔或進行專門的搜索來訪問所分享的內容。在訪問并考慮該內容時，其他成員可以通過采取一個或多個響應動作來做出反應，諸如提供關于該內容的反饋或看法。成員以這種方式交互的能力鼓勵他們之間的通信并且有助于實現社交網絡網站的目標。

社交網絡可以被建模為社交圖譜。諸如社交圖譜的節點圖譜可以包括極大數量的節點和連接節點的邊線。在社交網絡系統的情況下，用戶能夠訪問并分享在節點圖譜中反映的大量信息。例如，節點的數量可以是數億乃至數十億。這樣大量的數據的維護和提供存在許多挑戰。

發明內容

對于局部和平衡來動態映射節點，在實施方式中，計算機實現方法、系統和計算機可讀介質可以計算第一分區中的節點的柱狀圖(histogram)。可以計算第二分區中的節點的柱狀圖。基于第一分區中的節點的柱狀圖，第二分區可以被選擇為第一分區中的節點組(a set of nodes)的候選分區。基于第二分區中的節點的柱狀圖，第一分區可以被選擇為第二分區中的節點組的候選分區。基于負載平衡，第一分區中的節點組的至少一部分可以被映射至第二分區，并且第二分區中的節點組的至少一部分可以被映射至第一分區。

在實施方式中，可以計算第三分區中的節點的柱狀圖。基于第一分區中的節點的柱狀圖，第三分區可以被選擇為第一分區中的另一節點組的候選分區。基于第三分區中的節點的柱狀圖，第一分區可以被選擇為第三分區中的節點組的候選分區。基于負載平衡，第一分區中的另一節點組的至少一部分可以被映射至第三分區，并且第三分區中的節點組的至少一部分可以被映射至第一分區。

在實施方式中，第一分區中的節點組可以基于邊線局部的增益來分類。第二分區中的節點組可以基于邊線局部的增益來分類。

在實施方式中，基于與邊線局部的增益有關的概率，第二分區可以被選擇為第一分區中的節點的候選分區。

在實施方式中，第一分區中的節點的柱狀圖可以指出多個分區中的每個中的連接的節點的數量。

在實施方式中，重新映射至第二分區中的第一分區中的節點的數量和重新映射至第一分區的第二分區中的節點的數量之間的差值可以在閾值以內。

在實施方式中，第一分區中的重新映射至第二分區的節點的權重和第二分區中的重新映射至第一分區的節點的權重之間的差值可以在閾值以內。

在實施方式中，可以在重新映射之前計算第一分區的第一總節點權重。

在實施方式中，可以在重新映射之后計算第一分區的第二總節點權重。