本发明公开一种基于k-中心算法的网络中心选取方法,可以应用于分布式网络中,进而分配和利用这些中心进行网络设计等应用。
背景技术:
在通信网络中分配和利用中心是分布式网络设计中的主要问题。这些中心的各种应用包括分布式数据库、路由和分布式数据结构等场景。通过使用中心的集合,可以在完全集中的解决方案和完全分布式的解决方案之间提供便利的中间方法,并在容错需求和经济考虑之间实现合理的平衡。网络中心的选取是一个复杂而有意义的过程,它对研究一些大规模的网络具有重要的参考价值。在机器学习和数据分析领域,为了减小数据规模,研究人员通常会使用一部分点来代表整个数据集。然而,在实际应用中,会出现一些不公平和中心过载的情况,为了避免这种情况出现,发明新的网络中心选取方法迫在眉睫。
技术实现要素:
本发明的目的在于提供一种基于k-中心算法的网络中心选取方法,以解决上述背景技术中提出的现有的网络中心选取方法中出现的不公平和中心过载现象。
为实现上述目的,本发明提供如下技术方案:
一种基于k-中心算法的网络中心选取方法,其特征在于,包括以下步骤:
步骤一:通过一定的策略选取一个初始的网络中心集合;
步骤二:在初始的网络中心集合上得到公平的网络中心集合:该步骤使用了匹配的思想,在每个初始的网络中心的附近去匹配新的网络中心;
步骤三:得到结果:为了避免中心过载的情况,将步骤二中得到的公平的网络中心集合进行调整,使分配给每个网络中心的客户数量不超过容量上限。
步骤一的具体实现方法为:基于k-中心算法的基本思想,使用贪心的策略去选取初始网络中心集合,在这个过程中使用树结构记录选取网络中心点的先后次序。
步骤二的具体实现方法为:构造一个二部图去寻找公平的网络中心集合,二部图中的顶点分为两个部分,其中一部分是初始的网络中心集合,另一部分是不同类别的网络中心。如果初始的某个网络中心距离某个类别的点不超过给定的距离,将这两点间连接一条边。使用匹配算法可以得到公平的网络中心集合。
步骤三的具体实现方法为:基于步骤二得到的公平的网络中心集合,使用流算法改变客户到网络中心的分配方式,然后基于步骤一得到的树结构再次调整客户与网络中心之间的分配方式,便得到了公平且不会过载的网络中心集合。
具体实施方式
为使本发明的目的、内容和优点更加清楚,下面对本发明具体实施步骤作进一步详细的说明。
一种基于k-中心算法的网络中心选取方法,其特征在于,包括以下步骤:
步骤一:通过一定的策略选取一个初始的网络中心集合;
步骤二:在初始的网络中心集合上得到公平的网络中心集合:该步骤使用了匹配的思想,在每个初始的网络中心的附近去匹配新的网络中心;
步骤三:得到结果:为了避免中心过载的情况,将步骤二中得到的公平的网络中心集合进行调整,使分配给每个网络中心的客户数量不超过容量上限。
步骤一的具体实现方法为:基于k-中心算法的基本思想,使用贪心的策略去选取初始网络中心集合,在这个过程中使用树结构记录选取网络中心点的先后次序。
步骤二的具体实现方法为:构造一个二部图去寻找公平的网络中心集合,二部图中的顶点分为两个部分,其中一部分是初始的网络中心集合,另一部分是不同类别的网络中心。如果初始的某个网络中心距离某个类别的点不超过给定的距离,将这两点间连接一条边。使用匹配算法可以得到公平的网络中心集合。
步骤三的具体实现方法为:基于步骤二得到的公平的网络中心集合,使用流算法改变客户到网络中心的分配方式,然后基于步骤一得到的树结构再次调整客户与网络中心之间的分配方式,便得到了公平且不会过载的网络中心集合。
在步骤一中,具体包括:
在选取初始网络中心集合的过程中,使用了树结构记录选取的先后次序,具体表现为树中父亲和孩子的关系。
在步骤二中,具体包括:
在步骤一得到的初始网络中心集合的基础上,使用匹配算法得到公平的网络中心集合,在这个过程中使用了k-中心算法的阈值图方法,在假设已知最优解的情况下构造二部图。
在步骤三中,具体包括:
在步骤二得到的公平的网络中心集合的基础上,进行客户和网络中心之间分配方式的调整。在这个过程中还会选取一些新的网络中心为了避免出现中心过载的情况
本发明通过结合k-中心算法和匹配算法,可以高效地选取公平且不会过载的网络中心。
本发明提出的新型的网络中心选取方法,为分布式网络中选取网络中心提供了一种高效的方法。
1.一种基于k-中心算法的网络中心选取方法,其特征在于,包括以下步骤
步骤一:通过一定的策略选取一个初始的网络中心集合;
步骤二:在初始的网络中心集合上得到公平的网络中心集合:该步骤使用了匹配的思想,在每个初始的网络中心的附近去匹配新的网络中心;
步骤三:得到结果:为了避免中心过载的情况,将步骤二中得到的公平的网络中心集合进行调整,使分配给每个网络中心的客户数量不超过容量上限。
2.根据权利要求1所述的方法,其特征在于,步骤一的具体实现方法为:基于k-中心算法的基本思想,使用贪心的策略去选取初始网络中心集合,在这个过程中使用树结构记录选取网络中心点的先后次序。
3.根据权利要求1所述的方法,其特征在于,步骤二的具体实现方法为:构造一个二部图去寻找公平的网络中心集合,二部图中的顶点分为两个部分,其中一部分是初始的网络中心集合,另一部分是不同类别的网络中心。如果初始的某个网络中心距离某个类别的点不超过给定的距离,将这两点间连接一条边。使用匹配算法可以得到公平的网络中心集合。
4.根据权利要求1所述的方法,其特征在于,步骤三的具体实现方法为:基于步骤二得到的公平的网络中心集合,使用流算法改变客户到网络中心的分配方式,然后基于步骤一得到的树结构再次调整客户与网络中心之间的分配方式,便得到了公平且不会过载的网络中心集合。
技术总结