图聚类的新方法：LAMB-达CC

首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂439一种用于社区发现的相关聚类框架内特·威尔特普渡大学数学系印第安纳lveldt@purdue.edu西拉斐特David F. Gleich普渡大学印第安纳dgleich@purdue.edu西拉斐特Anthony Wirth计算机与信息系统学院墨尔本大学Parkville，VIC，Australiaawirth@unimelb.edu.au摘要图聚类或社区检测是在大型网络中识别密切相关对象组的任务在本文中，我们介绍了一个新的社区检测框架，称为LAMB-达CC，是基于一个特殊的加权版本的相关聚类。我们的方法中的一个关键组成部分是聚类分辨率参数λ，其隐含地控制由我们的框架形成的聚类的大小和我们表明，通过增加这个参数，我们的目标有效地在图聚类中的两种不同策略之间进行插值：找到稀疏割并形成稠密子图。我们的方法统一和概括了一些其他重要的聚类质量函数，包括模块化，最稀疏的切割，和集群删除，并将它们都放在一个优化问题的背景下，已经很好地研究了从近似算法的角度来看。我们的方法是特别相关的制度，找到密集的集群，因为它导致了2-近似的集群删除问题。我们使用我们的方法来聚类几个图，包括大型协作网络和社交网络。CCS概念• 计算数学→图论算法;近似算法;数学优化;关键词图聚类;社区检测;网络分析;相关聚类;簇删除;最稀疏割ACM参考格式：放大图片作者：David F.Gleich和Anthony Wirth。2018年。一种用于社区发现的相关聚类框架 在WWW 2018：2018年网络会议，2018年4月23日至27日，里昂，法国。ACM，New York，NY，USA，10页。https://doi.org/10.1145/3178876.31861101介绍识别网络中的相关实体组是跨科学学科的普遍任务。这项任务通常被称为图聚类，或社区检测，并可用于寻找类似的蛋白质在一个蛋白质相互作用网络，组相关的生物体本文在知识共享署名4.0国际（CC BY 4.0）许可下发布作者保留在其个人和公司网站上以适当的归属方式传播作品的权利。WWW 2018，2018年4月23日©2018 IW3C2（国际万维网会议委员会），在知识共享CC BY 4.0许可下发布。ACM ISBN 978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.3186110在食物网中，识别社交网络中社区，以及对web文档进行分类，以及许多其他应用。在图中定义正确的“好”社区概念一般来说，一个好的集群是集群内的节点彼此之间的连接比与图的其余部分的连接更紧密然而，关于确定网络聚类质量的最佳方法并不存在共识，最近的结果表明，由于人们可能对数据进行聚类的多种可能原因，不可能存在这样的共识[32]。 理论计算机科学家研究的常见目标函数包括归一化切割、最稀疏切割、电导和边扩展，所有这些都测量图中单个集群的切割尺寸比的某些版本。聚类质量的其他标准更加强调聚类的内部密度，例如聚类删除目标，它试图通过删除尽可能少的边将图划分为完全连接的节点集（集团）可以说，用于社区检测的最广泛使用的多聚类目标是由Newman和Girvan [31]引入的模块化。模块性测量给定划分的集群内的边缘的真实数量（“内部边缘”）减去内部边缘的预期数量之间的差异有有限数量的结果已经开始通过引入与模块化密切相关的目标函数来统一不同的聚类措施，并取决于可调的聚类分辨率参数[15，33]。Reichardt和Bornholdt开发了一种基于寻找无限程Potts自旋玻璃的最小能量状态的方法。他们研究的结果哈密顿函数被视为具有分辨率参数γ的聚类目标，其可用作检测网络中重叠和分层社区结构的启发式方法。当γ=1时，证明了极小化哈密顿量与求最大模块划分网络[33]后来，Delvenne et al.引入了一种称为聚类稳定性的度量，其概括了模块化，并且还与归一化切割目标和Fiedler的谱聚类方法有关，用于输入参数的某些值[15]。获得可证明接近最优解的聚类的固有困难使这些目标函数处于不利地位。虽然稳定性和哈密顿-波茨目标都为社区检测提供了有用的解释，但对于以下任一项都没有近似保证：所有当前的算法都是启发式的。此外，已知最大化首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂440±±IjIj.设为的补语而volbe它s∈\⊆2±..Σ2mIjIji≠j 一 –（1−x模块化本身不仅是NP难的，而且在任何常数因子内也是NP难的[19]。我们的贡献。在本文中，我们介绍了一个新的聚类框架的基础上，一个特殊的加权版本的相关聚类[4]。我们的分区目标签署网络在于“之间”我们的框架具有几个新的理论属性，并导致许多以前没有看到相关的聚类目标之间的连接总之，我们提供：一种新的框架ΛCC社区检测，是相关的模块化和哈密顿量，但更适合于近似结果。证明我们的框架在spars-est切割目标和集群删除问题之间插值，因为我们增加了一个分辨率参数λ。几个成功的算法优化我们的新ob-在理论和实践中的主观功能，包括节点被聚集在一起，但是如果它们是分开的，则W+。我们可以等价地将一致性权重定义为w+，如果i，j聚集在一起，但如果它们分开，则为wi−j。最大化协议和最小化分歧的最优聚类是相同的，但后者更难近似。相关聚类由Bansal等人引入，他证明了这个问题是NP完全的[4]。他们给出了一个多项式时间近似方案的最大化版本和常数因子近似最小化分歧的1加权图。随后，Charikar et al.给出了一个因素4近似最大限度地减少分歧，并证明了APX-硬度的这个变种。他们还描述了一般加权图中最小化的O（log n）近似[12]，由两个不同的小组独立证明，他们表明最小化分歧等价于最小多割[16，20]。该问题也被研究的情况下，边进行积极和消极的权重，满足概率约束条件：对于所有对i，j，w++w−=1。Ailon等人 给了2。5-i j i j2-这是聚类删除的近似，其改进了先前的最佳近似因子3。我们的方法在一些集群应用程序，包括社会网络分析和挖掘集团在协作网络中的演示。2背景和相关工作设G是n个结点V上的无向无权图，E有m条边.对任意v∈V，设dv是节点v给定SV，S=V S S（S）=v SDV音量. 对于每两个不相交的顶点集S，T，cut（S，T）表示S和T之间的边的数量。如果T=S¯，我们写cut（S）= cut（S，S¯）。设ES表示S的内边集。簇的边缘密度是密度（S）=|ES|/. |Σ，比值|Σ, the ratio该算法基于LP-松弛，并且另外开发了一种非常快速的算法，称为P IVOT，其预期给出3-近似[1]。目前，1实例上的相关性聚类的最佳近似因子略小于2。06，通过对正则LP松弛[13]的仔细舍入获得。2.2模块性和哈密顿量聚类质量的一个非常流行的度量是模块化，由Newman和Girvan [31]以其最基本的形式介绍我们更紧密地遵循New-man [30]给出的模块性的表示. 底层集群的模块化Q是：Q（x）=1i≠j Aij−Pij （1-xij），（2）其中如果节点i和j相邻，则Aij=1，否则为零，在S中的边的数量与节点对的数量之间。按照惯例，单个节点的密度为1。我们现在提出和xij和再次是二进制变量，指示背景和相关工作是我们结果的基础，包括对几个公共群集目标的定义。2.1相关聚类相关聚类的一个实例由符号图给出，其中每对节点i和j具有两个非负权重w+和w-，以指示相似性和不相似性。j在相应的聚类中。值Pij表示在特定的随机图模型中i和j之间存在边的概率该度量的目的是奖励聚类，其中聚类内的边的实际数量大于聚类中的边的预期数量，如由选择Pij。尽管存在许多选项，但在文献中设置 Pij=didj/（2m）是标准的，因为这既保留了Pij = di d j /（2 m），又保留了Pij = di d j/（2 m）。i j i j最大i和j度分布和期望的边缘数之间的分别是通常这些权重中只有一个对于每一对i，j都是非零的。目标可以表示为整数线性规划（ILP）：最小化。i外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂441.⊆||.{|| |}|||.||||...∈--..−′∈在一个节点上并且随机地均匀地跟随输出边，将在长度为t的随机游走之后结束于它开始的簇中。该t用作分辨率参数，因为当t增加时，步行者将倾向于“徘徊”得 Delvenne等人表明，目标（3）相当于特定时间步长范围t的稳定性度量的线性化版本[15]。2.3稀疏割和归一化割无符号网络G中的集群质量的一个度量是3λ1 6λ二个316λ16λ4λ2一个12λ4λ2214λ2λλ1λ1λ1λλλ1λλ1λλ图1：我们将玩具图（左）转换为标准（中）和度加权（右）LambdaCC的有符号图红色虚线表示负边缘。用G中的边和非边表示：最稀疏切割分数，针对集合S V定义为（S）=切割（S）/S+切割（S）/|S|（1）A（|S ||S|）的。期望（S）的值较小。λCC（x）=（i，j）∈E（1−λwiwj）xij+（i，j）gEλwiwj（1 −xij）（4）能够，因为它们表明S，尽管它的大小，只是松散地连接到图的其余部分。这一措施的差别在于 最多是相关边缘扩展度量的两倍：cut（S）/（min S，S¯）。如果我们在这两个目标中用vol（S）代替S，我们分别得到归一化切割和电导测量。在我们的工作中，我们专注于乘法缩放其中，X=（Xij）表示用于聚类的二进制距离。3.1连接到模块化尽管在方法和解释上存在显著差异，但是对于特定的选择，使分歧最小化的聚类与使哈密顿目标（3）最小化的聚类是相同的。我们称之为缩放最稀疏分割的目标ψ（S）=（S）/n=cut（S）/（S S¯），这与乘法近似下的最稀疏割相同最著名的是--参数为了看到这一点，我们在目标（4）中引入节点邻接值Aij，并执行几个代数步骤：图的最小最稀疏割的算法是O（，logn）-应用程序优化算法。[2]的文件。λCC（x）=（i，j）∈E（Aij−λwiwj）xij−（i，j）gE（Aij−λwiwj）（1−xij）2.4簇删除簇删除是找到最小数目的=（i，j）∈E（1−λwiwj）−。（Aij−λwiwj）（1−xij）。Ij删除G中的边，以便将G转换为不相交的集团集。这个问题首先由Ben-Dor等人研究。[6]，后来正式在工作的Natanzon等人。[29]，他证明了它是NP-难的，Shamir等人。[36]谁说的，那是一个很难的问题。后者研究的问题与其他相关的边缘修改问题，包括集群完成和集群编辑。许多固定参数的易处理性结果是已知的集群删除[8，14，23，24]，以及许多结果，关于特殊的图，其中的问题可以在多项式时间内解决[10，11，17，21]。Dessmark等人证明了递归地找到最大团将返回具有最优因子2内的聚类删除得分的聚类[17]，尽管通常该过程是NP-困难的。3理论成果我们的新聚类框架采用无符号图G=（V，E），并将其转换为相同节点集V上的有符号图G′=（V，E+，E-），用于固定的聚类分辨率参数λ∈（0，1）。关于相关聚类的划分G′选择Pij=wiwj/（2m）和γ=2mλ，我们看到：λCC（x）=（i，j）∈E（1 − λwiwj）+H（x）/2，（5）其中第一项只是常数。该定理如下：理论3.1.最小化L AM b DA CC对象的分歧等价于最小化H（x）。选择Pij=wiwj/（2m）让人想起最常用于模块化和哈密顿算子的图空模型。这最好地突出了这些目标与度加权ΛCC之间的相似性。3.2标准Lambda CC虽然度加权的ΛCC与模态和哈密顿量更密切相关，但标准ΛCC（对于每个v/V，设置w/v=1）导致最稀疏切割目标和聚类删除之间的强联系。该版本对应于解决相关聚类问题，其中所有正边缘具有相等的权重（1λ），而所有负边缘具有相等的权重λ。最小化分歧的目标函数是目标将导致G上的聚类。为了构造符号图，我们首先为每个v∈V引入节点权重wv。如果min（i，j）∈E+（1−λ）xij+（i，j）∈E−λ（1−x ij），（6）（i，j）E，我们在G′中的节点i和j之间放置一条正边，其中weight（1 λwiwj）. 对于（i，j）g E，我们在G中的i和j之间放置一条负边，其权重为λwiwj。我们考虑节点权重w v的两种不同选择：对所有v设置wv = 1（标准）或选择wv =dv （度加权）。在图1中，我们演示了这个过程将G转化为LΛ CC符号图G′。的目标LΛ CC是找到使G′中的不一致最小化的聚类，或者等价地使以下目标函数最其中我们包括与ILP（1）中相同的约束。这是单位权重相关聚类问题[4]（λ=1/ 2）的严格推广，表明该问题通常是NP-难的（尽管它允许几种近似算法）。 如果λ是0或1，则问题很容易解决：将所有节点放在一个群集中或将每个节点在单例集群中。通过选择λ的值而不是0、1/ 2或1，我们发现了在网络中识别稀疏割和找到密集子图之间的微妙联系。首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂4422--C {}.. ΣΣ−||.Σ||||--.ΣC={S，S，. . .，S}12k不超过∞22C.Σ−||--{*S，S}. ΣC∈C（S，S）− λ|S ||S|+ λ 2（1）A（|S ||S|）<λ当且仅当（7）小于λ n-λ|E|.如果我们设置λ′=（λ*+λ~）/2，则最优ΛCC聚类I=j=23.3连接到最稀疏的切割给定G和λ，由两个聚类生成的标准λ CC目标中的正边缘错误的权重=S，S′等于穿过切割的边缘的权重：（1 λ）截（S）。为了计算负边错误的权重，我们取整个网络中所有负边的权重λnE，然后减去S和S ¯之间的负边的权重：λS切割（S）。将所有项加在一起，我们发现该聚类的ΛCC目标是我们知道我们不能通过合并两个集群来降低目标，这意味着（1−λ）cu t（Si，Sj）−λ|SI||−λ cu t（S i，Sj）|−λcu t(Si,Sj)=cu t（Si，Sj）−λ|SI||≤0。|≤0.鉴于此，我们固定任意集群Si并对所有其他集群执行求和以查看.j≠icut（Si，Sj）−。j≠iλ|SI||≤0|≤0切¯。nΣ（七）=⇒cu t（Si，S¯i）−λ|SI||≤0 = ⇒ cu t（S i，S ¯ i）/。|≤0=⇒cut(Si,S¯i)/.|西||S¯i|Σ≤λ,注意，如果我们在所有2-聚类上最小化（7），我们解决了最小尺度稀疏切割问题的决策版本：代数的几个步骤证实存在某个集合S。ΣV带由于G是一个有限图，所以V的一个子集可以导出有限数量的缩放稀疏割分数。令λ~是所实现的第二小的缩放稀疏切割分数，因此λ~>λ*。以类似的方式，我们可以证明目标（6）等价于至少产生两个簇，因为λ′>λ*，并且每个簇具有最多λ′λ~处的缩放最稀疏切割。<通过我们选择λ〜，所有簇最小值1。切λ。。nΣ（八）返回的结果必须具有缩放的最稀疏割，且恰好等于λ*，其中2i=1（Si）−2i=1|SI||Si|+λ2-λ|E|、只有当返回的聚类具有两个聚类时才可能。因此，该聚类是网络的最小最稀疏切割分区其中，我们在G的所有聚类上最小化（注意，通过优化目标自动确定簇k的BER）。在这种情况下，最优求解目标（8）将告诉我们是否可以找到一个聚类，使得.k1cu t（Si，S¯i）/. . K1|SJ||Σλ。|Σ<λ. 因此，L和CC可以是陈述（b）如果λλ<*，形成单个簇必须是最优的。mal，否则我们可以调用语句（a）来断言存在一些非平凡的簇，其缩放的最稀疏割小于或等于而λλ*，则与λ*的极小性相矛盾。<如果λ=λ*，则形成a单个集群或使用集群C={S*，S¯*}产生相同的结果被视为决策版本的多聚类概括最小最稀疏切割。我们现在证明了稀疏割和ΛCC之间的更深层次的联系。使用度加权的ΛCC产生归一化切割的类似结果。理论3.2. 设λ*是图G的最小标度稀疏割值。(a) 对于所有λ>λ*，最优解（8）将G划分为两个或更多个簇，每个簇具有缩放的最稀疏割λ。存在一些λ′> λ*，使得LAM bDA CC是最小最稀疏割划分。(b) 当λ ≤ λ* 时，最好将所有节点放置在一个集群中。P屋顶。陈述（a）设S*是V的某个子集，它诱导a客观分数，出于同样的原因，这再次是最佳的。□3.4连接到群集删除对于较大的λ，我们的问题变得更类似于簇删除。我们可以通过取输入图G并在每对非相邻节点之间引入权重“”的负边来将任何簇删除问题简化为相关聚类。这保证了最优地解决相关聚类将产生全部对应于G中的团的聚类。此外，不一致的权重将是G中被切割的边的数量，即，聚类删除得分。我们可以通过选择每个负边的权重来为α<∞。相应的目标是斯帕尔斯特卡特岛例如，（1）A（1）A（2）A（|S *||）= λ *。|)=λ∗. 对应于C={S*，S¯*}的L和CC目标为. Σ2（i，.j）∈E+ xij+--（i，.j）∈E−α（1 −xij）。（十）cu t（S *）−λ|S *||+λ n −λ|E|.|.（九）如果我们代入α=λ/（1λ）我们看到这与目标（6）不同只有一个乘法常数，因此是等价的当最小化目标（8）时，我们总是可以获得λnλ E，将所有节点放入单个集群。但是请注意，聚类的得分¯在表达式（9）中严格地小于λ n − λ|E|对于所有λ> λ*。即使{S*，S¯*}不是最优的，这意味着当λ>λ* 时，我们可以做得比把所有节点放在一个集群中更好。在这种情况下，让*是最优的LAMB-DA CC集群，并考虑其集群中的两个：Si和Sj。Si和Sj之间不一致的权重等于它们之间的正边的数量乘以正边的权重：（1λ） cut（Si，Sj）。如果我们通过合并Si和Sj来形成新的聚类，则这些正的不一致将消失;反过来，我们将引入λ|SI||−λ cu t（S i，S j）n w个错误，b eing nega-|−λcu t(Si,Sj)n ewmistakes,b eingnega-聚类之间的有效边缘因为我们假设C*是最优的近似项。当α>1时，将不同的节点将比切割正边缘更昂贵，因此我们将预期优化λ CC目标的聚类将G分离成“接近”集团的密集聚类我们用一个简单的定理和推论将其形式化。理论3.3. 如果最小化无符号网络G =（V，E）的CC目标，则C中每个簇的边密度至少为λ。P屋顶。取一个簇S并考虑如果我们将S分解，使其每个节点都被放置到自己的单例集群中会发生什么。这意味着我们现在在之前S中的每个正边缘处都犯了错误，这增加了权重KK-λ|E|.证明了缩放的最稀疏切割上的期望上限首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂443C∈--联系我们∈∈-||联系我们2222M+1. ΣIjIjIjJKik它必须是非负的，因为C是最优的，所以|ES |− λ|S|≥0，（ii）w++ w++w−cij+cjk+cik归一化切割模块性学位-算法1t三个LP加权λ=0标准联系我们2mλ二分之一Mm+11输入：符号图G′=（V，E+，E−），λ（0， 1）输出：G′的聚类求解ILP（6）的LP松弛，获得距离（xij）设G~=（V，F+，F-），其中F+= （i，j）：xij1/ 3和<5：F−= （i，j）：xij1/ 3将PIVOT应用于G~。最稀疏切割相关聚类簇删除图2：对于λ（0，1）的特定值，Lambda CC等效于其他几个目标。值λ*和ρ*不是先验已知的，但可以通过求解λ的值越来越小的LambdaCC来获得。表1：对于λ（0，1），标准Lambda CC已知的最佳近似因子，用于最小化不一致和最大化一致。当λ > 1 / 2时，我们贡献了两个常数因子近似以最小化不一致。λ∈（0， 1/ 2）λ= 1/ 2λ∈（ 1/ 2， 1）最大银0的情况。7666[37] PTAS[4] 0的情况。7666[37]民迪斯时间复杂度为O（log n）[12，16，20]2。06[13]3.2：λ>mΣ4算法我们提出了几个新的算法，专门为我们的LΛ CC框架，一些来近似保证，一些是专为效率。1我们的前两种方法依赖于vanZuylen和Williamson的一个关键定理，它可以用来证明使用旋转算法的相关聚类的不同情况下的近似结果，该算法通过选择枢轴节点k，将其与其所有正邻居聚类，并在图的其余部分上递归。如果枢轴被随机均匀地选择，这对应于Ailon等人的P IVOTALM。[1]的文件。为了完整起见，我们在这里陈述定理，并进行了微小的更改以匹配我们的符号和表示：理论4.1. （[38]中的定理3.1）设G=（V，W+，W-）是一个带符号的加权图，其中每对节点（i，j）都有正的和负的负权重w+ ∈ W+和w− ∈ W −。给定一组LP成本（1λ）ES。另一方面，S中的节点之间不再有负错误，因此LΛ CCcij：i V，j V，i≠j，且无权图G~=（V，F+，F-）满足以下假设：(i) 对于所有（i，j）∈F+，wi−j≤αcij，且.. |S |ΣΣ通过粉碎S所产生的物镜的总变化为w+≤αcij对于所有（i，j）∈F−，目标将同时减少λ2- -|ES|.i j。Σ~（1 −λ）|ES |− λ.. |S |Σ−|ES|ES|ES| − λ. |S |Σ. Σ对于G中的每个坏三角形：（i，j），（j，k）∈F+，（i，k）∈F−，则将P IVOT应用于G ~将返回花费α的解。ijcij这意味着密度（S）=|ES|//下一页|S|≥ λ。□C〇 rllARY 3.4。设G有m条边。对于每个λ>m/（m+1），优化LAM b DA CC等同于优化簇删除。P屋顶。所有输出聚类必须具有至少m/（m+1）的密度，这仅在密度实际上为1时才可能，因为m是图中的边的因此，所有簇都是团，并且Λ CC和簇删除目标仅相差乘法常数（1-λ）。□3.5等价和近似我们在图2中总结了Λ CC与其他目标之间的等效关系。伴随着这一点，表1列出了最知名的近似结果，用于最大化标准Lamb的一致性和最小化分歧。van Zuylen和Williamson [38]给出了一个完整的证明，他们还包括一个确定性地选择枢轴以实现相同近似的策略。4.1 λ CC的3近似为了应用定理4.1，我们必须计算LλCC的LP松弛（6）（其中cij是边（i，j）的成本）以获得距离xij，然后我们将其舍入为未加权图G~。如果我们可以构造G~来满足定理的假设，则所有剩下的是应用PIVOT以产生期望的近似结果。我们的第一方法的伪代码显示在算法1中，我们称之为三个LP，因为它满足以下应用程序最大化保证：理论4.2.算法THreeLP满足定理4.1，其中α=当λ>1/2时，标准L AM b DA CC为3。一个CC符号图。对于度加权的Λ CC，最好的-对于所有λ的已知近似因子是O（log n）[12，16，20]，用于最小化分歧，以及0。7666最大化协议[37]。因此，由于加法常数，ΛCC比模块化（和相关）更易于1对于我们工作的最初提交，我们通过改变Charikar等人的方法，当λ> 1/2时提出了λ CC的5-近似和簇缺失的4-近似。[12 ]第10段。在这里，我们展示了改进的近似，我们开发的基础上，一个有用的建议，从一个匿名的评论。 我们将原始近似结果包含在我们论文的完整版本中[39]。≤α期待中首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂444.∈≥Ij∩∈不超过∈Ij∈{} ∈∈--.ΣIjIjIjIjIjJKikIjJKikP屋顶。我们开始陈述定理4.1的符号与针对下式的边权重和LP成本之间的对应关系：LAMBDA CC.图G′=（V，E+，E−）由正权值为（1−λ）的边和权值为λ的负边，因此cij=（1−λ）xij和（w+，w−）=（1−λ， 0）如果（i，j）∈E+• 通过求解簇删除的LP松弛开始：minimize（i，j）E+xij受xij ≤xik+xjk，对于所有i，j，kxij∈[0， 1] for all（i，j）∈E+xij= 1 for all（i，j）∈E−（十四）cij= λ（1 − xij）和（w+，w−）=（0，λ）如果（i，j）∈ E−。通过构造，如果（i，j）∈F−则xij1/ 3，否则（i，j）∈F+<•定义F+={（i，j）：xij1/ 2}，F−={（i，j）：xij≥1/ 2}。<如前所述，然后在G~=（V，F+，F−）上运行PIVOT。我们命名为结果程序TWOCD，并证明以下结果：我们知道xij1/ 3。我们需要检查定理4.1的前两个不等式是对于所有（i，j）∈F+（ 11），wi−j≤αcijw+≤αcij ， 对 于 所 有 （ i ， j ） ∈F−（ 12）其中α=3。如果（i，j） F+ E+，则wi−j=0且不等式（11）是平凡的，因为左边是零。类似地，不等式（12）是平凡的，如果（i，j）∈F−∩E−。假设（i，j）∈F+∩ E−。则wi−j=λ且cij=λ（1 −xij），我们知道xij<1/3 =⇒（1 −xij）>2/3。因此：wi−j=λ<3 λ（2/3）<3 λ（1 −xij）=αcij。另一方面，如果（i，j）∈F−∩E+，则w+ =（1−λ），cij=理论4.3. 算法TwoCD返回2-近似的簇删除。P屋顶。首先观察到通过对G ~执行P ivot不会产生负边缘错误：如果k是枢轴并且i、j是G ~中k的两个正邻居，则xik <1/2，xjk < 1/2，xijxik+xjk1。<因为所有的距离都小于1，所以所有的节点必须共享G′中的正边，因为对任何（i，j）E−xij=1。证明的其余部分从示出新构造的图G ~ G是新构造的图开始。当α=2时，满足定理4.1的假设。为了节省篇幅，我们将细节推迟到论文的完整版本[39]。□这一结果是特别有趣的，因为没有常数因子近似的集群删除已明确预先。（1−λ）xij，且xijI j≥1/ 3，所以我们看到：在以前的文学作品中。2到目前为止，相关聚类的最佳近似值比任何已知的结果都要强w+=（1 −λ）= 3（1 −λ）（1/3）≤ 3（1 −λ）xij=αcij。这就完成了不等式（11）和（12）的证明。接下来，我们考虑一个三元组的节点i，j，k，其中（i，j）F+，（j，k）F+，但（i，k）F-。这被称为坏三角形，因为当聚类G~时，我们将不得不违反这些边中的至少一个。我们必须证明：w++w+ +w−≤3。cij+cjk+cikΣ，（13）对于簇删除，我们的结果表明，后者的问题也许是更容易的两个近似。4.3可扩展的启发式算法作为一个对应的以前的近似驱动的方法，我们提供了快速算法的基础上，贪婪的本地启发式的ΛCC。其中第一个是GrowClUSTER，它迭代地这显示起来有些乏味（13）中的变量高度依赖于原始符号图G′中节点i、j、k之间共享的边的类型;对于总共八种情况，每条边有两种可能性。我们在这里给出了第一个例子的证明。情形1：假设（i，j）∈ E+，（j，k）∈ E+，且（i，k）∈E−。 对于这种情况，我们注意到（cij，cjk，cik）=（（1−λ）xij，（1 −λ）xjk，λ（1 −xik））且（w+，w+，w-）=（1-λ，1-λ，λ）。通过我们对F+的构造通过贪婪地聚合相邻节点来在其周围进行，直到对ΛCC目标没有更多的改进。其变体称为GROWCLIQE，专门设计用于簇缺失。它单调地改进了Λ CC目标，但不同之处在于，在每次迭代时，它均匀地随机选择k个未聚类的节点，并且贪婪地围绕这些种子中的每一个增长集团。所得到的集团可能会重叠：在每次迭代中，我们只选择最大的集团。和F−，我们知道xij1/ 3，xjk1/ 3，通过三角不等式，我们有xik≤xij+xjk2/ 3。<<<结合这些事实：3（cij+cjk+cik）= 3 （1−λ）（xij+xjk）+λ（ 1−xik）≥3（（ 1−λ）xik+λ（ 1−xik））= 3（（ 1− 2λ）xik+λ）> 3（（1 − 2 λ）2/3 +λ）= 2 −λ=w++w++w−。最后，由于ΛCC和哈密顿目标是等价的，我们可以使用先前开发的算法和软件用于具有分辨率参数的模块化目标。特别是，我们采用的Louvain方法，由Blondel等人开发的算法的适应。[7]的文件。它迭代地访问图中的每个节点，并将其移动到相邻的集群，如果这样的移动给出模块性得分的局部最大增加。这我是随机均匀选取一个未成簇的节点组成簇首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂445--继续，直到没有移动增加模块化，此时我们依赖于上面的事实，即（1 2λ） 0，这将我们的证明限制在λ>1/ 2的情况< 由于空间限制，我们将其他七种情况的证明推迟到论文的完整版本[39]。□集群被聚合成超级节点，并且整个过程在聚合网络上重复通过调整原始的Lou- vain方法，使贪婪的局部移动的基础上的LΛ CC目标，而不是模块化，我们得到了一个可扩展的算法4.2聚类删除的2-近似为了获得用于簇删除的近似算法，我们以两种方式改变三个LP2van Zuylen和Williamson关于约束相关聚类的结果可用于获得聚类删除的3-近似（[38]中的定理4.2），尽管在他们的工作中没有明确提到聚类删除。首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂446已知其为相关对象提供良好的近似，并且另外很好地适应我们的参数λ的变化。我们称之为L ambda-LOUVAI n。该算法的标准和度加权版本都可以通过采用现有的广义Louvain算法（ 例 如 ， Jeub 等 人 的 GenLouvain 算 法 。 http ：//netwiki.amath.unc.edu/GenLouvain/). 我们的启发式算法满足以下保证：理论4.4.对于每个λ，算法GrowClUT er和21.51.01.05.25.5.7.921.51枢轴ThreeLPGrowClusICM拉姆卢夫.01.05.25.5.7.9λ*λλ*λLAM b DA-Lo U v AI n将所有节点放置在一个集群中，或者它们产生具有由λ界定的缩放的最稀疏切割的集群。当算法贪婪地优化度加权的ΛCC时，归一化割的类似结果成立。 我们在论文的完整版本中提供了详细的证明[39]。5实验我们首先比较我们的新方法对现有的相关聚类算法在几个小的网络。这说明（a）空手道，n=34，λ*=。026721.51.01.05.25.5.7.9（b）《悲惨世界》，n=77，λ*=。004521.51.01.05.25.5.7.9我们用于ΛCC的算法优于常见的替代方案。λ*λλ*λ然后，我们研究了众所周知的图划分算法如何隐式地优化各种λ的ΛCC目标。在亚（c）Polbooks，n=105，λ*=。0069（d）足球，n=115，λ*=。0184随后的实验中，我们将我们的方法应用于集团检测的协作和基因网络，社会网络分析。5.1小型网络上的LambdaCC在我们的第一个实验中，我们表明，Λ-L OUVAI n是最好的通用相关聚类方法，最大限度地减少了Λ CC目标。我们在四个小型网络上进行了测试：[26]《易经》：“君子之道，焉可诬也？有始有卒者，其惟圣人乎！”，13.14冉子退朝。 图3显示了我们的算法P IVOT和ICM在λ值范围内的性能。Pivotis是AILON等人的快速算法。[1]，它选择一个均匀的随机节点，并将其邻居与之聚类。ICM是Bagon和Galun [3]的能量最小化启发式算法。我们发现，在实践中，三个LP给出了比3个应用程序更好的效果PIVOT快得多，但对于接近0或1的λ表现不佳。ICM也比求解LP松弛快得多，但在可扩展性方面仍然有限，因为它旨在用于大多数边权重为0的相关聚类问题（对于ΛCC不是这种情况）。另一方面，GrowCluster和Λ- LOUVAL是可扩展的，并且对于所有输入网络和λ的值给出良好的近似。5.2标准聚类算法许多现有的聚类算法隐式地优化ΛCC目标的不同参数制度。我们通过在由BTER模型生成的1000节点合成图上运行几种聚类算法来证明这一点[35]。我们在来自arXiv电子印刷网站的ca-GrQc协作网络的最大组件（4158个节点）上做同样的事情然后，我们针对λ值的范围计算每个算法的Λ我们首先使用Graclus [18]（形成两个集群），Infomap [9]和Louvain [7]对每个图进行聚类。为了形成密集簇，我们还通过递归地提取最大团（称为RMC）和通过递归地提取最大准团（RMQC）来划分网络，即，最大内缘密度节点集图3：我们在四个小型网络上使用五种相关聚类算法优化了标准LambdaCC目标。y轴报告每个算法的得分与通过求解LP松弛确定的最优目标的下限之间的比率Lambda-LoU vain（黑色）和GrowCLU s ter（紫色）除了是最可扩展的算法之外，对于所有λ都表现良好在每个图中，虚垂直线指示最佳缩放最稀疏截值λ*。下面有一个ρ<1的界（这里我们使用ρ= 0。（六）。最后两个过程必须在每一步解决NP难目标，但对于合理大小的图，存在可用的团和准团检测软件[28，34]。在每个算法产生了无符号网络的单个聚类之后，我们评估该聚类的ΛCC客观得分如何随着我们改变λ而变化。这允许我们观察算法是否有效地近似λ值的一定范围的Λ为了比较，我们针对λ的每个不同值运行Λ-L_ out。图4报告了每个聚类的ΛCC客观评分与LP松弛下限之间的比率这些图说明，我们的框架和Λ-LOUVAI η有效地插在图分区中的几个完善的策略之间，并且可以作为已知这些算法中的任何一个有效的任何聚类任务的良好代理。5.3大型协作网络中的簇删除ΛCC和簇删除之间的联系为