复杂网络图的最大匹配

-22Journalof King Saud University沙特国王大学沙特国王大学学报www.ksu.edu.sawww.sciencedirect.com复杂网络图的最大匹配纳塔拉詹·梅加纳坦Jackson State University，Jackson，MS 39217，美国接收日期2015年5月27日;修订日期2015年10月12日;接受日期2015年2015年12月2日在线发布摘要我们将复杂网络图的最大相似性匹配问题定义为使构成匹配的端顶点的相似性最大化的问题。在这种追求中，我们引入了一个度量，称为边的权重，定义为未覆盖的相邻边的数量与端顶点的权重差的绝对值的乘积。MAM算法优选地在每次迭代中包括具有最小可重构性权重的边缘（每次迭代一个边缘），直到覆盖所有边缘。MAM算法还可以适于确定最大分解匹配（MDM）以最大化作为匹配的一部分的端顶点之间的相异性，以及确定简单地最大化作为匹配的一部分的顶点的数量的最大节点匹配（MNM）。我们在真实世界的网络图以及基于理论模型的随机网络图和无标度网络图上运行MAM，MNM和MDM算法，并分析节点匹配%和重复性指数之间的权衡（目标最佳值：MAM为1， MDM为©2015作者制作和主办由爱思唯尔B.V.代表沙特国王大学。 这是CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍图G=（V，E）的匹配M是边E的子集，使得M中没有两条边有公共顶点。最大匹配是一组独立的边，使得任何附加的边到集合的包含违反匹配的性质（在集合的任何两个边之间没有公共顶点）。一个图的匹配称为最大匹配，如果每个电子邮件地址：natarajan. jsums.edu沙特国王大学负责同行审查图中的顶点可以通过一组边与图的另一个顶点匹配，使得该组中没有两个边具有公共顶点。图的顶点可能存在各种大小的最大匹配;但是，每个最大匹配不一定是最大匹配;另一方面，图中顶点的最大匹配是图中顶点的最大可能最大匹配。因此，我们将最大匹配问题称为找到其端顶点形成非重叠节点对的独立边的最大集合的问题，使得节点对的最大数目是V，如果数目为如果顶点数为V，则顶点数V是偶数，并且是V-1，很奇怪一个著名的算法，用于寻找最大的独立边缘的最大集合，以实现任意的节点匹配http://dx.doi.org/10.1016/j.jksuci.2015.10.0041319-1578© 2015作者制作和主办由爱思唯尔B.V.代表沙特国王大学。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词最大匹配;搭配匹配;分解匹配;搭配指数;复杂网络;节点相似度复杂网络图的最大匹配231---网络图是在V个顶点的图上的时间复杂度为O（V4）的Blossom 算法（Edmonds，1965 ）。一些改进（例如，Micali和Vazirani）到Blossom算法的改进。所有这些算法的一个弱点是，在追求最大的节点匹配，很少考虑的顶点之间的相似性匹配。如在本文的模拟中所观察到的，复杂网络图中的顶点的最大或最大节点匹配不需要匹配可比较节点权重的顶点（例如，节点度）。本文提出的研究动机源于这一观察。我们想要确定彼此非常相似（或彼此非常不相似）的顶点的最大匹配（不需要是最大匹配，但足够接近最大匹配）。这相当于最大化（或最小化）构成匹配的边的称为重复性指数的度量。到目前为止，在复杂网络图的文献中，仅在网络级（Newman，2002）和节点级（Piraveenan等人，2008，2012），但不是关于顶点的匹配。我们的论文是这方面的第一篇论文。一组边的相似性指数（相对于节点权重的任何特定度量折射率指数值的范围可以从1到1。如果相对于节点权重的特定度量计算的一组边的关联性指数接近1，则它意味着形成该组的边的端顶点相对于节点权重的特定度量彼此非常相似（例如，高度数顶点匹配到另一个高度数顶点，低度数顶点匹配到另一个低度数顶点等）。如果重性指数接近于0，则边集中的顶点的配对相对于节点权重是任意的。另一方面，如果边的集合相对于节点权重的度量的不确定性指数接近于1，则意味着构成边集合的大多数节点对相对于节点权重彼此不相似（例如，如果节点度被用作节点权重，则边集合的重复性指数1意味着构成边集合的大多数节点对相对于节点权重彼此不相似）。在该集合中涉及匹配到低度数顶点高度数顶点，反之亦然）。对于社交网络和其他复杂的现实世界网络，其中对等交互和协作是优选的，将彼此非常相似（或非常不相似）的顶点配对作为网络中顶点的最大匹配的一部分可能是有用的。在社交网络中，关于被匹配的顶点的权重是任意的最大匹配不需要是优选的。例如，一个已经取得了一些成就的研究人员可能想与另一个也有类似研究概况的研究人员配对（比如在一个研究领域的同行评议出版物数量方面量化），这样他们就可以相互合作并相互受益。另一方面，一个新加入社交论坛（如researchgate.net或linkedin.com）的研究人员可能希望与一个有成就的研究人员配对。如果社交网络中的每个节点一次只能与另一个节点匹配，则必须匹配彼此相异或彼此相似的节点（取决于兴趣的应用）;社交网络中顶点的任意匹配可能没有任何实际益处。据我们所知，我们还没有遇到一个最大匹配算法，最大化的重复性指数（匹配节点彼此相似）或最小化重复性指数（匹配节点彼此非常不同）在复杂的网络图。在本文中，我们提出了一个最大匹配算法，可用于最大化或最小化的边缘构成的匹配确定在复杂的网络图中的节点的权重（在节点权重的差异越小，越相似的节点，反之亦然）的重性指数。作为匹配的一部分的边被称为覆盖自身以及覆盖原始图中与其相邻的边，并且这些边不能是匹配的一部分。我们定义了一个度量，称为边的权重，它是图中与该边相邻的未覆盖边的数量与构成该边的端顶点的权重差的绝对值的乘积。用于最大化重复性指数的最大匹配算法（以下称为最大重复性匹配算法MAM）优选包括具有较低重复性权重的边缘作为匹配的一部分。算法在迭代中运行。在每次迭代中，我们根据上面定义的重复性权重度量确定图中未覆盖边的排名，并选择重复性权重度量值最小的边，并将其包括在构成匹配的边中。我们继续迭代，直到图中的所有边都被覆盖。具有最小值的权重的边可能具有较少的相邻边，并且包括具有足够接近的节点权重的端顶点。我们的假设是，对于足够密集的图，通过选择具有较小的重复性权重值的边，我们可以同时最大化匹配的重复性指数以及最大化作为匹配的一部分选择的边的数量。该算法对于社交网络和其他现实网络中的点匹配具有重要的应用价值。我们的算法将是第一个这样的算法，它基于边的可重性权重的概念来确定顶点的最大匹配，并且不使用增强路径的概念（Cormen等人，2009），如大多数现有匹配算法所使用的。我们评估了所提出的最大重复匹配（MAM）算法在六个真实网络图上的性能，这些网络图的度分布范围从泊松（随机网络）Strang，2005到幂律（无标度网络）（Caldarelli，2007），以及在从理论模型模拟的复杂网络上运行该算法，例如我们观察MAM算法来确定节点的最大匹配（每个节点对的端顶点彼此相似），并且匹配的总体重复性指数明显大于仅以最大化匹配节点数量为本文的重点是提出了最大化匹配的协调性指数在论文的结尾232N. 梅加纳坦我们还表明，该算法可以用于最小化匹配的匹配性指数（最大分解匹配），只需包括具有最大分解权重的边缘作为每次迭代中匹配的一部分（不需要其他修改）。第二节讨论了相关的工作，并强调了本文的贡献。第三节提出了任意图的最大节点匹配（MAM）算法，并讨论了它作为最大匹配算法（以下简称MNM）的可扩展性。第4节给出了MAM和MNM算法在度分布从Poisson到幂律的真实网络图上的结果。第5节和第6节分别给出了在按Erdos-Renyi模型生成的随机网络上，以节点度为节点权值和随机权值的MAM 和MNM 算法的实验第7节给出了在根据Barabasi-Albert模型生成的无标度网络上执行MAM和MNM算法的结果。第8节介绍了一种最大分解匹配算法（称为最大分解匹配算法，MDM）的修改，以确定目标为最小化分解指数的匹配，并介绍了在第4第9节总结论文。在整个论文中，术语意思是一样的2. 相关工作在用于社交网络分析的感兴趣的图之前，考虑用于最大匹配的图通常是二部图，其中存在两组顶点（在同一组中的顶点之间没有边）并且边将顶点从一组连接到另一组。给定一个没有边权重的二分图，最大匹配问题将是关于确定图的两个集合中顶点之间的最大匹配数量。如果一个二分图的边都有权值，那么最大匹配问题就是确定匹配边的集合（集合中没有两条边有重叠的顶点），使得边权值之和最大。二部图的最大匹配问题可以使用著名的多项式时间算 法 （ 如 Edmonds-Karp 算 法 （ Edmonds and Karp ，1972））来最优地解决二部图的最大匹配问题迄今为止还没有被文献考虑过。相反，一个称为稳定匹配问题的相关问题被考虑用于二分图，并被定义如下：给定二分图的两个分区的每个顶点的偏好集，如果不存在任何顶点对（A，B）使得A匹配，则从一个分区到另一个分区的顶点匹配被认为是稳定的匹配到比B更不优选的某个其他顶点，同样地，B匹配到比A更不优选的某个其他顶点。Gale-Shapley算法（Shoham和Leyton-Brown，2009）是用于在两个部分中具有相等数量的顶点的偶图中进行稳定匹配的众所周知的选项。我们没有看到任何可能的扩展，这个算法或任何其他稳定的匹配算法提出的二分图，以确定最大的排斥或最大dissorta- tive匹配任意网络图。如果有向网络图需要最大匹配，文献中的常见策略是得到网络图的二分等价，并应用Edmonds-Karp或任何其他算法来确定二分图中的最大匹配。确定有向图的二部等价的问题是一个NP困难问题（Kalman，1963）。Guillaume andLatterfly（2006）提出了一种使用团覆盖的启发式算法，用于将有向图转换为二分图。在Chatterjee等人（2013）中，使用结构可控性的概念提出了一种替代策略（Liu等人， 2011）来确定有向复杂网络图中的最大匹配，绕过了首先转换为二分图的需要。该算法的目标是最大化作为匹配的一部分的节点的数量，而不是被设计为最大化或最小化重复性指数。在Wang et al.（2011）中，作者表明，对于具有二项度分布的网络，最大和最小的重复率随网络的密度而变化。受这一观察的启发，Winterbach等人（2012）引入了一种算法，使用度保持重布线（Maslov和Sneppen，2002）和加权b匹配（Muller-Hannemann和Schwartz，1999）来计算给定有效节点度向量的具有最大或最小重复性的网络。保度链路重布线可以有效地降低或增加网络图的可达性，而不 影 响 顶 点 的 度 分 布 。 然 而 ， Wang 等 人 （ 2011 ） 和Winterbach 等 人 （ 2011 ） 的 工 作 都 没 有 得 到 证 实 。（2012）可以被扩展以确定图的边的最大分类匹配。Wanget al.（2011）还表明，对于度分布为二项分布的网络（如基于Erdos-Renyi模型的随机网络图），最大关联性和最小关联性是渐近反对称的。这一观察结果与我们在第8节中的观察结果有很好的相关性，即最大排斥匹配的排斥指数的值与最大排斥匹配的排斥指数的绝对值具有足够的可比性，特别是在随机网络图具有随机节点权重以及节点度作为节点权重的情况下。Piraveenan等人（2012）探索了复杂网络中的度可归性，并提出如果网络可以被分割成子网络，则完美度可归性是可能的，其中每个子网络是完整网络;另一方面，完美度可归性被认为在复杂网络中相对更难实现，除了完全二分图的情况（Van Mieghem et al.，2010）（像一个星形图）。尽管在所有类型的复杂网络中都很难观察到完美度分解性和完美度分解性，但在本文中，我们证明了有可能找到一个顶点匹配，使得分解指数显着接近最优值（特别是在最大分解匹配的情况下）。在Holme和Zhao（2007）中，作者在给定的复杂网络图（从理论模型生成）上反复使用度保持链路重布线，以获得图的集合，并测量集合复杂网络图的最大匹配2332222图;聚类性和聚类系数的值的范围越宽，原始图的度分布就越窄，反之亦然。在8.4节中，我们讨论了无标度网络中MAM和MDM的协配性指数值（根据节点度计算）之差与节点度的谱半径比之间的相关性。我们证明，除了额外考虑聚类系数（如Holme和Zhao，2007）之外，最大分离匹配和最大分离匹配的重复性指数值可以用来表征无标度网络的度分布变化。对于构成匹配的边缘集合，确定具有最小基数的最大匹配的问题是NP困难问题（Yannakakis和Gavril，1980）。它等价于寻找最小边支配集的问题（Horton and Kilakos，1993 ） 我 们 论 文 中 的 焦 点 问 题 是 最 大 独 立 边 集 问 题（Cormen等人，2009），其中我们要找到最大的一组独立的边缘，使没有两个边缘有一个共同的端点。请注意，物流（例如，Cardinal等人，2005）不能应用于确定最大节点匹配和最大a（di）选择匹配。因为，最小边集问题的算法更可能确定边的集合，使得集合中的每个边本文提出的最大匹配算法采用优先包含覆盖较少相邻边的边的方法，以使确定的独立边的数目尽可能大。据我们所知，我们还没有遇到一个最大的匹配算法，旨在同时最大化的a（di）sortativity的匹配，以及最大化的基数匹配复杂的网络图。从这个角度来看，本文提出的最大分解匹配和最大分解匹配算法是对复杂网络图和分析文献的重要贡献。3. 最大似然匹配算法3.1. 网络模型和定义我们将输入网络图G=（V，E）建模为顶点V和无向边E的集合，其中每个顶点V具有权重w（v）R。我们说一条边（p，q）与一条边（r，s）相邻，如果p，q，r，s为V且p=r或p=s或q=r或q=s。也就是说，两条边（p，q）和（r，s）被称为彼此相邻，如果它们有一个共同的端点。虽然边是无向的，但为了讨论起见，我们将边（u，v）中指示的第一个顶点（顶点u）称为上游顶点，将边（u，v）中指示的第二个顶点（顶点v此外，由于边是无向的，我们方便地采用一种约定来表示边：边（u，v）的上游顶点的ID总是小于边的下游顶点的ID（即，

下载后可阅读完整内容，剩余1页未读，立即下载