[發明專利]一種基于k-中心算法的網絡中心選取方法

在審

• 申請號: 202110514339.3
• 申請日: 2021-05-08
• 公開（公告）號: CN113206889A
• 公開（公告）日: 2021-08-03
• 發明（設計）人: 吳小良;鄒美標;郭雨田
• 申請（專利權）人: 中南大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開一種基于k?中心算法的網絡中心選取方法，可以應用于分布式網絡中，進而分配和利用這些中心進行網絡設計等應用。本發明利用k?中心算法和匹配算法，可以得到公平且不會過載的網絡中心集合，能應用于機器學習、人工智能和數據分析等領域。

技術領域

本發明公開一種基于k-中心算法的網絡中心選取方法，可以應用于分布式網絡中，進而分配和利用這些中心進行網絡設計等應用。

背景技術

在通信網絡中分配和利用中心是分布式網絡設計中的主要問題。這些中心的各種應用包括分布式數據庫、路由和分布式數據結構等場景。通過使用中心的集合，可以在完全集中的解決方案和完全分布式的解決方案之間提供便利的中間方法，并在容錯需求和經濟考慮之間實現合理的平衡。網絡中心的選取是一個復雜而有意義的過程，它對研究一些大規模的網絡具有重要的參考價值。在機器學習和數據分析領域，為了減小數據規模，研究人員通常會使用一部分點來代表整個數據集。然而，在實際應用中，會出現一些不公平和中心過載的情況，為了避免這種情況出現，發明新的網絡中心選取方法迫在眉睫。

發明內容

本發明的目的在于提供一種基于k-中心算法的網絡中心選取方法，以解決上述背景技術中提出的現有的網絡中心選取方法中出現的不公平和中心過載現象。

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

一種基于k-中心算法的網絡中心選取方法，其特征在于，包括以下步驟：

步驟一：通過一定的策略選取一個初始的網絡中心集合；

步驟二：在初始的網絡中心集合上得到公平的網絡中心集合：該步驟使用了匹配的思想，在每個初始的網絡中心的附近去匹配新的網絡中心；

步驟三：得到結果：為了避免中心過載的情況，將步驟二中得到的公平的網絡中心集合進行調整，使分配給每個網絡中心的客戶數量不超過容量上限。

步驟一的具體實現方法為：基于k-中心算法的基本思想，使用貪心的策略去選取初始網絡中心集合，在這個過程中使用樹結構記錄選取網絡中心點的先后次序。

步驟二的具體實現方法為：構造一個二部圖去尋找公平的網絡中心集合，二部圖中的頂點分為兩個部分，其中一部分是初始的網絡中心集合，另一部分是不同類別的網絡中心。如果初始的某個網絡中心距離某個類別的點不超過給定的距離，將這兩點間連接一條邊。使用匹配算法可以得到公平的網絡中心集合。

步驟三的具體實現方法為：基于步驟二得到的公平的網絡中心集合，使用流算法改變客戶到網絡中心的分配方式，然后基于步驟一得到的樹結構再次調整客戶與網絡中心之間的分配方式，便得到了公平且不會過載的網絡中心集合。

具體實施方式

為使本發明的目的、內容和優點更加清楚，下面對本發明具體實施步驟作進一步詳細的說明。

一種基于k-中心算法的網絡中心選取方法，其特征在于，包括以下步驟：

步驟一：通過一定的策略選取一個初始的網絡中心集合；

步驟二：在初始的網絡中心集合上得到公平的網絡中心集合：該步驟使用了匹配的思想，在每個初始的網絡中心的附近去匹配新的網絡中心；

步驟三：得到結果：為了避免中心過載的情況，將步驟二中得到的公平的網絡中心集合進行調整，使分配給每個網絡中心的客戶數量不超過容量上限。

步驟一的具體實現方法為：基于k-中心算法的基本思想，使用貪心的策略去選取初始網絡中心集合，在這個過程中使用樹結構記錄選取網絡中心點的先后次序。