我们有后来被分解为高内聚性集群的社交图。 Jonathan Cohen [1]称之为桁架。图中的命名集群
既然我有这些集群，我想为他们想出名字。 群集名称应允许对群集大小进行无意义的更改，而不更改名称。
例如： 假设我们有集群L：
M : {A, B, C, D, E, F}
，让我们假设“命名算法”生成的名称“M”它。
在一段时间之后，顶点A离开该群集，而顶点j具有加入：
M : {B, C, D, E, F, J}
新近生成的名称为 “m””。
需要的功能：
m' == m for insignificant cluster changes
[1] http://www.cslu.ogi.edu/~zak/cs506-pslc/trusses.pdf
根据你的榜样，我假设你的意思是 “微不足道的变化，以集群组成”，不给 “簇大小”。
如果命名功能f()不能使用有关给定集群的现有名称的信息，你就必须让，有时它虽然变化是小的重命名。事实上，假设f()从来没有当它稍微改变时重命名一个集群。从集群A开始，您可以通过一次只添加或删除一个元素来访问任何其他集群B.通过构造，该函数将为A和B返回相同的名称。由于A，B是任意的，因此f()将为所有可能的群集返回相同的名称 - 显然无用。
所以，你有两个选择：
（1）命名功能依赖于集群的现有名称，或
（2）的命名函数有时（很少）后重命名集群非常微小的变化。
如果使用替代方法（1），它很简单。您可以简单地随机分配名称，并且只要群集更新，只要它们不太相同（不过您定义的不同），就可以保持它们不变。鉴于它很简单，我想这不是你想要的。
如果使用替代方法（2），则需要使用有关集群中基础对象的一些信息。如果你所有的链接都是不带内部结构的各种对象的链接，那么它就不能完成，因为除了集群大小之外，该函数没有任何东西可用。
假设你有一些关于物体的信息。例如，你可能有他们的名字。呼叫第一个k字母的每个对象的名称对象的前缀。计算您的群集中所有不同的前缀，并找到最常见的。按字母顺序排列这些n前缀，并按顺序将它们追加到对方。对于合理选择k,n（应取决于您的群集数量和典型对象名称长度），只要您在每个群集中有足够的对象，就会得到您要查找的结果。例如，如果对象具有人名，则尝试k = 2;如果对象具有人名，则尝试3。如果你有上百个集群，也许尝试N = 2
这当然也可以通过重新映射名被大大提高，实现了更均匀的分布，其中处理两个前缀具有相同频率的情况下，等