社交网络中极化和不同意见的最小化

Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France3690在社交网络中最小化极化和不同意见0Cameron Musco麻省理工学院（MIT）cnmusco@mit.edu0Christopher Musco麻省理工学院（MIT）cpmusco@mit.edu0Charalampos E. Tsourakakis波士顿大学（BU）ctsourak@bu.edu0摘要0社交媒体和在线社交网络的兴起对社会产生了颠覆性的影响。意见越来越多地受到在线社交媒体上的互动塑造，包括不同意见和极化现象现在紧密地融入到日常生活中。在这项工作中，我们开始研究以下问题：0给定n个代理人，每个代理人都有自己关于一个话题的核心价值的初始观点，以及一个意见动态模型，那么最小化不同意和争议同时存在的社交网络的结构是什么？这个问题对于推荐系统来说至关重要：推荐系统是否应该偏好在两个在线用户之间提供相似观点的链接建议，以保持不同意见的低水平，还是在两个用户之间提供不同观点的链接建议，以使每个用户接触到其他人的世界观，并降低整体的极化和争议水平？这样的决策对社会有重要的全局影响[48]。我们的贡献包括将这个问题作为一个优化问题进行数学形式化，并提出了一个精确、时间高效的算法。我们还证明了总是存在一个具有O(n/ϵ^2)条边的图，它是最优解的(1+ϵ)近似。我们的公式是图拓扑优化的一个实例，参见[6, 11,45]。此外，对于给定的图，我们展示了如何在多项式时间内优化相同的目标。最后，我们对我们提出的方法在合成和真实数据上进行了实证研究，验证了它们作为挖掘工具的价值，以更好地理解不同意见和极化之间的权衡。我们发现，在现实世界的网络中，减少争议和不同意见的空间很大；例如，在Reddit网络上，用户在政治问题上交换评论，我们的方法实现了争议和不同意见的减少，数量级为6.2×10^4。0CCS概念0• 计算数学 → 图算法；0关键词0社交网络；意见动态；极化；优化0ACM参考格式：Cameron Musco，Christopher Musco和Charalampos E.Tsourakakis。2018年。在社交网络中最小化极化和不同意见。在WWW0本文发表在知识共享署名4.0国际许可下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW 2018，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/https://doi.org/10.1145/3178876.318610302018：2018年网络会议，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/https://doi.org/10.1145/3178876.318610301 引言0社交媒体和在线社交网络的巨大流行已经导致了人们分享和形成观点方式的根本变化。一些事件在网上引发了激烈的辩论，例如谷歌的詹姆斯∙达莫尔内部备忘录泄露在网上，显示出社会和社交媒体用户在有争议的问题上变得极化[12]。不同意见和极化等社会现象已经存在于人类社会中几千年了，现在它们发生在一个在线虚拟世界中，对社会产生了巨大的影响。此外，意见越来越多地受到社交媒体的影响。因此，Facebook的推荐系统最近被指责在美国全国选举期间传播假新闻和俄罗斯广告，从而引发了关于科技巨头在社会中的作用的额外争议[46]。谷歌也面临类似的指责，指责其影响选举结果[41]。从商业角度来看，推荐系统旨在通过优化与点击率和用户参与度相关的数学目标来最大化收入-有些是短期的，有些是长期的。然而，鉴于像Facebook和谷歌这样的科技巨头的日益强大，需要更好地了解推荐链接对社会的影响[47]。以下事实激发了我们的工作。ValdisKrebs分析了亚马逊上的购买趋势。他发现在2008年总统选举期间，已经支持巴拉克∙奥巴马的人倾向于购买描绘他的正面形象的书籍。同样，不喜欢他的人，购买描绘他的负面形象的书籍[29，第1章]。这种偏见被称为确认偏见[30]，它是阴谋论和假新闻传播的根源。简而言之，大多数人避免挑战自己的观点。因此，一个在真实数据上训练的推荐系统，其目标是最大化收入和增加用户参与度，可能自然地最终创建“回声室”。同样，在社交网络的背景下，更喜欢具有相似心态的用户之间的连接，而不是具有不同心态的用户之间的连接。另一方面，最小化不同意见会导致更大的极化。为了直观地理解这一点，考虑一个有两种主要观点的话题，比如支持民主党或共和党政治。当用户连接到具有相似心态的用户时，形成了两个具有强烈和极端观点的群体，导致两个群体之间的更大极化[5]。这种极化对社会有害；例如，达到政治目标的3700一致性变得更加困难。这种分歧和极化之间的权衡激发了我们的研究。我们有兴趣了解最小化分歧和极化的社交网络结构。我们引入并研究了两个关键问题，如下所述。对于这两个问题，我们使用弗里德金-约翰森模型[21]作为我们的基本观点动力学模型，该模型包括分歧和共识，因为它将每个节点与固有观点和表达观点相关联。详见第2节。0•在图上最小化极化和分歧。我们首次研究了社交网络中推荐连接对社会的全局影响的重要问题。我们对这个问题进行了数学形式化，并通过证明我们的优化公式是凸的，提供了一个多项式时间算法。我们的公式是图拓扑优化的一个实例。对于其他类似的优化问题，请参见[6,11, 45]。0问题1.给定n个代理，每个代理都有反映其在某个主题上核心价值的初始观点和观点动力学模型，具有给定总边权重的连通社交网络的结构如何最小化极化和分歧？0我们还证明，总是存在一个具有最多O(n/ϵ^2)条边的图，可以对上述问题进行(1+ϵ)近似。也就是说，通过非常稀疏连接的网络可以最小化分歧和极化。0•在观点上最小化极化和分歧。我们还研究了以下优化问题。在这里，社交网络是给定的，我们希望修改代理的固有观点，以在平衡状态下最小化极化和分歧。这个问题旨在理解旨在影响固有观点的定向广告或推荐的效果。0问题2.给定一个网络G，其中有n个代理，每个代理都有自己的初始观点、观点动力学模型和预算α>0，我们应该如何使用总观点质量不超过α来改变初始观点，以最小化极化和分歧？0•实验。我们在合成和真实数据上评估了我们的方法。我们的研究结果表明，我们的图优化方法可以显著降低Twitter和Reddit上的极化和分歧水平，并证实我们的方法可以作为挖掘工具来更好地理解链接推荐的影响。我们还实验观察到，现有的图拓扑与最小化极化和分歧相差甚远。例如，我们的提出的方法显示，通过优化Reddit数据集的图拓扑，我们可以将极化和分歧减少6.2×10^4倍。0路线图。本文的组织如下：第2节介绍相关工作。第3节介绍我们的算法贡献。第4节介绍合成和真实数据的实验结果。最后，第5节总结本文。0符号。我们在整篇论文中使用以下符号。设G(V,E,w)为一个加权连通无向图，其中V=[n]，|E|=m。设N(i)为节点i的邻域，w_ij为其度数。设A为邻接矩阵，L为组合拉普拉斯矩阵。这里D=diag(d(1),...,d(n))是一固有0设L0为组合拉普拉斯矩阵。这里D=diag(d(1),...,d(n))是一个对角矩阵，其对角线上是度数。每个代理i∈V都有一个固有观点s_i∈[0,1]。设s=(s_1,...,s_n)∈[0,1]^n为固有观点的向量。最后，设�1，�0分别为全1和全0向量。02相关工作0据我们所知，我们是第一个正式定义和研究第1节中提出的问题。接下来我们回顾相关工作。0建模意见动态。意见动态一直是政治学家、经济学家、社会学家、物理学家、控制系统科学家和计算机科学家等的研究热点。意见动态模型社会学习过程。这样的模型在理解政治投票（例如[1,8]）、病毒营销（例如[14]）和社交媒体中发生的各种现象（例如[40]）方面具有重要应用。存在离散和连续模型。在前者中，代理人只有两种可能的观点，0或1。在后者中，观点跨越一个连续范围；文献中常见的选择是区间[0, 1]和[-1,1]。选民模型是一种常见的离散模型，最初由Clifford和Sudbury[10]在动物之间的领土冲突背景下描述。一般来说，离散模型应用各种可能更新代理人观点的交互机制。这些机制包括随机采用相连邻居的观点或应用局部多数规则[18]。0DeGroot在他的工作中引入了连续的意见动态模型。0关于共识形成的开创性工作[16]。社会中的一组n个个体从一个主题的初始观点开始。个体观点通过固定社交网络的邻域的平均值进行更新。Friedkin和Johnsen[22]将DeGroot模型扩展为包括不同意见和共识，通过将每个个体的固有信念与某个权重混合到平均过程中。我们将在下面更详细地讨论这个模型。其他连续模型包括Hegselmann-Krause模型[28]和Deffuant-Weisbuch模型[49]。Das、Gollapudi、Munagala使用了一个将连续和离散方法结合起来以更好地拟合意见数据的模型[14]。Bhawalkar、Gollapudi、Munagala研究了网络和代理人观点共同演化的情景[?]。0值得一提的是，意见形成的许多方面已经被纳入现有模型中，例如意见领袖、外部影响等。我们建议感兴趣的读者参0已经将意见领袖、外部影响等纳入现有模型中。我们建议感兴趣的读者参考Mossel和Tamuz的综述以及其中的参考文献，了解更多关于意见动态模型的相关工作[34]。0Friedkin-Johnsen意见动态。每个节点维护一个持久的内部（或固有）观点si，保持不变。节点通过重复平均化来更新其表达观点zi。更具体地说，如果wij≥0是边(i,j)∈E上的权重，N(i)表示节点i的邻域，则在一个时间步骤中，代理人i将其观点更新为平均值0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France3710zi=0si+�0j∈N(i)wijzj01+0j∈N(i)wij.0设z�为该过程的平衡点。平衡时的值z�i是节点i的表达观点。众所周知，平衡点z�是线性方程组的解：0z�=(I+L)−1s [Friedkin-Johnsen平衡] (1)0这里，L是连接图G的组合拉普拉斯算子。注意，(I+L)始终可逆，因为它是正定的（实际上，它的所有特征值都大于或等于1）。Friedkin-Johnsen模型已被Bindel等人用作理解社会中自私地更新观点以最小化经历的压力时的混乱代价的模型[4]。这里，压力由两个项组成，即节点i在平衡时可能表达与其固有观点不同的观点的压力，以及其表达观点与其邻居的表达观点之间的差异。形式上，节点i的压力定义为(z�0Tsaparas等人使用这个模型提出了一种影响最大化的变体[27]。0极化。Munson等人创建了一个浏览器小部件，根据用户阅读的新闻文章来衡量用户的偏见，并建议阅读相反观点的文章以减少极化[35]。Liao和Fu提供了一个工具，让用户意识到他们观点的极端性，以及根据他们在该主题上的专业知识来合理地证明观点[33]。Dandekar等人定义了一个增加不同意指数的极化观点形成过程，并展示了现有线性模型捕捉极端极化的局限性，并提出了一个非线性模型[13]。Flaxman等人通过研究浏览历史来研究政治“回声室”，并展示了关于社交网络如何影响人们观点的一些有趣的实证结果[20]。0与我们的工作最接近的是Matakos等人的工作[?]。在他们的工作中，他们提出了一种改进的影响0他们关注Friedkin-Johnsen模型下平衡向量  z � 的  ℓ 2范数，这与我们在第3.1节中介绍的极化度量接近，只是他们没有对观点向量进行均值中心化。给定参数  k ，他们考虑选择一组  k个节点，使得如果将它们的固有观点设为零，所提出的极化指数将被最小化。这个问题是NP难的，仅关注极化，而不考虑不同意见。在概念层面上，与我们的工作相近的还有Garimella、Morales、Gionis和Mathioudakis的工作[24]，他们关注Twitter数据。Garimella等人从Twitter数据中创建图形，提出了极化的新定义，并根据这个度量检测引起激烈辩论的话题。在后续工作中，他们考虑了减少极化的链接推荐问题[25, 26]。0最后，使用真实数据进行观点动态分析的一个重要方面是考虑时间因素[38]。0数据的观点挖掘是一个重要的问题。例如，我们如何将推文映射到观点，即实数？自然语言处理（NLP）社区在这个领域做了很多工作；请参考0关于情感分析和Twitter观点挖掘的更多细节，请参考Nakov的最新调查[36]。0图拓扑优化。问题1（见第1节）旨在优化图拓扑上的目标。我们回顾了一些相关的图拓扑优化问题的实例，其中大部分位于图挖掘文献之外，后者主要关注边推荐而不是全局结构结果。02009年，Daitch、Kelner和Spielman提出了学习图的方法[6]。0为了利用图挖掘技术进行机器学习，需要找到适合向量点的图形，他们提出了目标函数||LX  || 2 [11]。0其中  L  是图拉普拉斯矩阵，  X  是数据矩阵的表示[4]。0他们的目标是最小化所有点的重构误差，其中点的重构误差是点与其邻居的加权平均值之差的  ℓ 2范数。其他研究小组也考虑了相关方法；例如，参见[17, 31]。0系统发生学中的核心问题是学习进化树[2]。0解释观察到的  n物种存在的进化树。一种流行的技术是基于距离的技术；找到一个进化树（其叶子对应于物种），它与一组0对于机器学习而言，最重要的问题是学习配对基因距离[19]。0学习图模型的广泛技术（例如Chow-Liu）通过优化问题在图拓扑上学习图模型[32]。Boyd等人研究了在图上找到最快混合的马尔可夫链的问题[6,45]，将其作为在给定图的所有可能加权子图上的优化问题。03提出的方法03.1极化和不一致性0根据Friedkin-Johnsen模型，对于社交网络G（V，E，w）和内在观点s：V→[0，1]，令z� =（I + L）-1s为观点的均衡向量。0不一致性。我们将边（u，v）的不一致性d（u，v）定义为u，v在均衡时观点的平方差：d（u，v）0def = wuv（z�u -z�v）2。我们将总不一致性DG，s定义为：0DG，s = �0（u，v）∈Ed（u，v）。[不一致]（2）0极化。直观上，极化应该衡量均衡时观点与平均观点的偏离程度。有许多方法可以量化这一点。我们选择方差的标准定义，即观点的二阶矩。具体来说，令¯z为均值中心化的均衡向量：0¯z = z� - z�T0�1。0然后极化PG，s定义为：0PG，sdef = 0u∈V¯z2u = ¯zT¯z [极化]（3）0Track：社交网络分析和Web的图算法WWW 2018年4月23日至27日，法国里昂Observation 1. The disagreement DG,s is a quadratic form. Specif-ically, DG,s = z∗T Lz∗, and by Proposition 3.1, DG,s = ¯zT L¯z.Recommended linkPG,sDG,sIG,s(1, 2)0.66700.667(1, 3)0.1110.2220.333(2, 3)0.1110.2220.333Table 1: Trade-off between polarization and disagreementfor three agents with innate opinions s1 = s2 = 0,s3 = 1.For details, see Section 3.1.3.2Optimizing over Graph TopologiesUsing the definitions of Section 3.1, we can now formulate Problem 1from Section 1 mathematically. The objective is to minimize thesum of two terms, polarization and disagreement. Here, L is theset of valid combinatorial Laplacians of connected graphs. Observethat the trace of the Laplacian is equal to twice the total edge weightof the corresponding graph.Problem 1minL∈Rn×n¯zT ¯z + ¯zT L¯zsubject toL ∈ LTr(L) = 2m(5)Note that by (3) and Observation 1, ¯zT ¯z + ¯zT L¯z = DG,s + PG,s,where G is the weighted graph corresponding to the Laplacian L.Thus (5) is equivalent to minimizing the polarization-disagreementindex IG,s over all graphs G with total edge weight m.Theorem 3.3. The objective ¯zT ¯z + ¯zT L¯z is a convex function ofthe edge weights in the graph G corresponding to the Laplacian L.Proof. Using Proposition 3.2 we rewrite the objective as:¯zT ¯z + ¯zT L¯z = ¯sT (I + L)−1(I + L)−1¯s + ¯sT (I + L)−1L(I + L)−1¯s= ¯sT (I + L)−1(I + L)(I + L)−1¯s = ¯sT (I + L)−1¯s.It is known that the function f (L) = (I + L)−1 is matrix-convexwhen L ∈ L and hence positive semidefinite [? ]. That is, for anyλ ∈ (0, 1),λZ−11+ (1 − λ)Z−12⪰ (λZ1 + (1 − λ)Z2)−1.This gives that xT (I + L)−1x is convex for all vectors x ∈ Rn.□Additionally, the set of Laplacians L which we optimize over isconvex (standard fact).Claim 1. The set Ldef= {Ln×n : L Laplacian, Tr(L) = 2m} is convex.By Theorem 3.3 and Claim 1 we obtain that Problem 1 is solvablein polynomial time. One may use gradient descent or second ordermethods, see [7]. In the following, we show how to compute thegradient in a closed form in order to perform gradient descent moreefficiently (compared to relying on numerical approximations of it).Gradient. Let N =�n2�, and ei be the i-th standard basis vector inRN . We can write L = B diag(w)BT where B ∈ Rn×N is the signoriented incidence matrix and w ∈ RN is the vector of edge weightsfor the graph G corresponding to L. Let bi be the i-th column of B,i = 1, . . . , N. Observe that the graph Laplacian corresponding toTrack: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France3720现在我们介绍极化-不一致性指数，即我们关心的目标。0IG，s def = PG，s + DG，s [极化-不一致性指数]（4）0有两个有用的命题和一个观察结果。0命题3.1. 不一致性DG，s满足方程：0DG，s =0�0（u，v）∈E0wuv（¯zu -¯zv）2。0证明。令µ0def =0n是z�的均值，所以第i个坐标是i - µ。现在，观察到wuv（¯zu0¯z的第i个分量是¯0观察1. DG，s是一个二次型。具体来说，DG，s =0µ - z�v + µ）2 = d（u，v）。通过对所有边求和得到结果。□0命题3.2. 令¯s = s - sT� 10n� 1是均值中心化的内在观点向量。0观点向量。然后，¯z =（I + L）-1¯s。0证明。对于任何图形，L� 1 = 0。因此（I + L）� 1 = � 1，或等价于0静默� 1 =（I + L）-1� 1。这意味着z�T� 1 = sT（I + L）-1� 1 = sT�1。根据这些事实，我们得到0¯z = z� - z�T0n0� 1 =（I + L）-1s - z10n0� 1 =（I + L）-1s -sT� 10n0� 10=（I +L）-1�0s -0� 1 T s0n0�0�0=（I + L）-1¯s。0□0命题3.2提供了计算¯z的另一种方法。我们可以通过显而易见的方式找到它，即找到z�然后将其以零为中心。或者，我们可以先将s以零为中心，然后在内在观点向量为¯s时获得¯z作为Friedkin-Johnsen均衡。0极化和不一致性之间的权衡。在进入任何技术细节之前，我们展示一个简单的例子，说明了极化和不一致性之间的权衡。假设有三个代理人，其中两个对某个主题持有观点0，而另一个对该主题持有观点1，即s =[0，0，1]。我们希望在这三个代理人之间推荐一条权重为1的链接。与人类确认偏见一致的推荐是节点1和2之间的边。均衡观点向量与s相同，即z� = [0，0，1]。总不一致性为0，极化等于（-1/3）2+（-1/3）2 +（2/3）2 =0.667。另一个选择是推荐节点1，3之间的边。现在的均衡是[1/3，0，2/3]。总极化等于0 2 +（-1/3）2 +（1/3）2 =0.222。总不一致性为（2/3 - 1/3）2 =0.111。因此，第二个推荐结果在极化和不一致性之和方面取得了更好的结果。根据对称性，边（2，3）具有与边（1，3）相同的效果。结果总结在表1中。the weight vector w + ϵei, is L + ϵbibTi . Hence, if we perturb thei-th coordinate of any weight vector by ϵ, i.e., to w + ϵei we obtainthe Laplacian L + ϵbibTi . The Sherman-Morrison formula for thematrix pseudo-inverse yields:(I + L + ϵbibTi )+ = (I + L)−1 − ϵ(I + L)−1bibTi (I + L)−11 + ϵbTi (I + L)−1bi,and hence, thinking of (I + L)−1 as a matrix-valued function of w,∂(I + L)−1∂wi=limϵ→01ϵ(I + L)−1 − ϵ(I + L)−1bibTi (I + L)−11 + ϵbTi (I + L)−1bi− (I + L)−1=λf (L1) + (1λ)f (L2)f (λL1 + (1λ)L2)L1 =1−10−12−10−112−1−1−110−101(1ϵ′)xT (L + I)xxT ( ˜L + I)x(1 + ϵ′)xT (L + I)x →Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France3730− ( I  +  L ) − 1 b i b T i0因此，根据线性性质和定理3.3中所示的  ¯ z T ¯ z  + ¯ z T L ¯ z  =  ¯s T ( I  +  L ) − 1 ¯ s ，我们有：0∂ s T (1 s 。0∂ w i =  − s T ( I  +  L ) − 1 b i b T i ( I+  L ) − 1 s 。0非凸性。令人惊讶的是，我们的目标稍微更一般的形式，其中两个项中的一个乘以任意因子  ρ  ≥  0（即，极化和不一致性的权重不同），是非凸的！0定理3.4. 令  ρ ¯ z T ¯ z  +  ¯ z T L ¯ z ,  ρ  ≥  0 为我们的目标。对于 ρ  =  0 ，该目标是边权的非凸函数。0证明。根据命题3.1和3.2，我们得到：0z � T Lz � =  ¯ z T L ¯ z  =  ¯ s T ( I  +  L ) − 1 L ( I  +  L )− 1 ¯ s 。0为了证明这是非凸的，只需证明  f  ( L )  = ( I  +  L ) − 1 L ( I  +  L )− 1 是非凸的。设  L 1 ,  L 2  ∈ L 。为了推导矛盾，假设  f  ( L )  =( I  +  L ) − 1 L ( I  +  L ) − 1 是凸的。那么，对于任意  λ  ∈  ( 0 ,1 ) ，根据凸性有：0λ ( I  +  L 1 ) − 1 L 1 ( I  +  L 1 ) − 1 +  ( 1  − λ )( I  +  L 20( I  +  λL 1  +  ( 1  −  λ ) L 2 ) − 1 ( λL 1  +  ( 1  −  λ ) L 2 )( I  +0取  λ  =  0 . 5，考虑以下两个对应于3个节点上的两条路径的拉普拉斯矩阵：0������� ，  L 2= �������0�������。0可以通过数值验证得到，λ ( I  + L 1 ) − 1 L 1 ( I  + L 1 ) − 1 +  ( 1− λ )( I  + L 2 ) − 1 L 2 ( I  + L 2 ) − 1 −  ( I  + λL 1  + ( 1  − λ ) L2 ) − 1 ( λL 1  +  ( 1  − λ ) L 2 )( I  +  λL 1  +  ( 1  − λ ) L 2 ) − 1的最小特征值是负数。这与  f  ( L )  的凸性假设相矛盾。□0我们注意到可以轻松构造出其他 ρ值的更多反例（细节略）。最后，我们证明总是存在一个具有  O ( n0ϵ 2  ) 的边，其在乘法意义下与最优解相差不超过  ( 1  ±  ϵ  +  O (ϵ 2 ))  倍。0最优的——即近似最小化极化-不一致性指数  I G , s不需要一个稠密图  G。我们的证明依赖于关于谱稀疏化的开创性工作[ 3 ,  42 – 44]。下一个定理证明了一个关于图  G边数的次优结果，但使用了Spielman和Srivastava提出的基于有效电阻的稀疏化算法，该算法具有快速和易于实现的优点[42]。0定理3.5. 总是存在一个具有  O ( n  log n / ϵ 2 ) 条边的图  G，其极化-不一致性指数  I G , s  达到问题1的最优解的  ( 1  +  ϵ  +O ( ϵ 2 ))  倍。0证明。设  L  是最小化极化和不一致性之和，同时满足总边权约束  m 的拉普拉斯矩阵，即满足 (5)的解。通过将Spielman-Srivastava算法应用于  L ，并设置误差参数ϵ ′ ，我们得到一个谱稀疏化矩阵，其组合拉普拉斯矩阵  ˜ L对于任意  x  ∈  R n  满足：0( 1  −  ϵ ′ ) x T Lx  ≤  x T  ˜ Lx  ≤  ( 1  +  ϵ ′ ) x T Lx。 (6)0这反过来意味着，01 + ϵ' x T (L + I) - 1 x ≤ x T (˜L + I) - 1≤ 101 - ϵ' x T (L + I) - 1x。0通过设置 x = s，OPT def = s T (L + I) - 1 s，并使用分数1的泰勒展开式01 - ϵ' = 1 + ϵ' + O(ϵ'^2) 当 ϵ' 很小时，我们得到 s T (˜L + I) - 1 s≤ � 1 + ϵ' + O(ϵ'^2) � ∙ OPT。0注意我们可能没有 Tr(˜L) = 2m。然而，根据 (6)，Tr(˜L) ≤ (1 + ϵ') Tr(L) = (1 +ϵ')2m。因此，我们可以缩放˜L使得Tr(˜L) = 2m，仍然有 s T (˜L + I) - 1 s ≤ 101 + ϵ' ∙ � 1 + ϵ' + O(ϵ'^2)0OPT ≤ � (1 + ϵ + O(ϵ^2)) � ∙ OPT，如果我们设置 ϵ' =0那么 s T (˜L + I) - 1 s ≥ s T (L + I) - 1 s = OPT，因为 L 是 (5)的最优解。□0如前所述，我们在证明中使用了Spielman-Srivastava稀疏化算法[42]，因为我们在实验中使用了它。然而，由于Batson-Spielman-Srivastava的后续结果[3]将边的数量减少到与节点数量成线性关系。使用相同的数学论证，但是使用[3]而不是[42]，我们得到了定理3.5的以下推论。0推论3.6. 总是存在一个具有 O(n/ϵ^2)条边的图，使得极化-不一致性指数 I_G, s在问题1的最优解的乘法因子 (1 + ϵ + O(ϵ^2)) 范围内。03.3 优化内在观点0接下来，我们给出问题2的数学形式。我们展示如何简化这个形式，以获得一个凸优化程序（具体来说，是一个SDP），可以使用标准算法在多项式时间内解决[7]。方程 (7)提供了一种直接的建模方法来描述我们的问题。我们希望最小化极化和不一致性的总和，同时考虑动态所暗示的结构和总变化 α的总预算。我们优化的变量是ds，即观点的变化。我们限制这个变化使得内在观点减少，即 ds ≤ �0。(7)(8)ER(0.5)PL(2)PL(2.5)PL(3)L∗L∗-sparsifieds ∼ PL(1.5)14.3816.1022.0653.0511.6011.60s ∼ PL(2)25.9845.1672.11107.2319.2419.27sPL(2.5)94.87103.62121.21166.3885.5585.563740问题20最小化 ds ∈ R n ¯ z T ¯ z + ¯ z T L¯ z，满足 z � = (I + L) - 1 (s + ds)0n � 1 � 1 T ds ≥-α ds ≤ � 0 s +ds ≥ � 00我们的主要结果是以下命题。0命题3.7. 在 (7) 中问题2的公式是可解的0在多项式时间内。0证明。我们可以使用我们的分析简化 (7) 的目标0来自第3.2节。具体而言，我们的问题等价于0最小化 (s + ds) T (I + L) - 1 (s + ds)0满足 ds ≤ � 0 � 1 T ds ≥-α s + ds ≥ � 00通过展开上述目标，我们观察到它是一个标T x + c，其中 Q0def = (I + L) - 1 是对称的0正半定，b = (I + L) - 1 s 和 c = s T (I + L) - 1s（注意b，c与变量ds无关）。这个目标是凸的，并且约束集形成一个凸集，证明了命题。□0我们注意到上述凸形式 (7) 可以适应其他类型的约束，例如限制 ds0修改其他类型的约束，例如限制 ds的值在特定范围内，或允许内在观点的正向变化。在我们的实验部分中，我们使用基本的公式而没有额外的约束。04 实验结果04.1实验设置0数据集。我们使用De等人收集的两个数据集[15]。具体来说，De等人收集用户生成的文本以及他们之间的互动[15]。使用NLP工具[39]将文本映射为观点，并使用互动创建用户之间的网络。有许多预处理细节，可以在[15]中找到。在这里，我们对两个数据集进行简要描述。0Twitter是一个具有n = 548个节点和m = 3,638条边的网络。0边对应于用户之间的互动。我们可以获得所有节点的观点。该数据集旨在分析关于2013年德里立法议会选举的Twitter辩论。这是一个没有解决的事件，三个主要政党获得了大致相等的选票份额。用于收集推文的标签是#BJP，#APP，#Congress，#Polls2013，时间跨度为12月9日至15日。0Reddit是一个具有n = 556和m = 8,969条边的网络。有0如果存在两个用户在给定时间段内都在两个（除了政治以外的）subreddit中发布帖子，则它们之间存在一条边。感兴趣的主题是政治。0除了上述真实数据集之外，我们还使用了各种合成数据。由于大多数现实世界的网络具有偏斜的度分布，我0合成数据的广泛多样性。由于大多数现实世界的网络具有偏斜的度分布，我们专注于使用Norros-Reittu模型[38]生成的幂律随机网络，这是一个重要的随机模型。0提出的方法0表2：随机幂律观点向量的极化-不一致性最小化。Erdös-Rényi、随机幂律图以及我们对问题1的解决方案生成的最佳图L � 和˜ L �-sparsified的平均极化-不一致性指数IG，s在5个实验中。行对应于根据幂律分布（斜率分别为1.5、2和2.5）生成固有观点s。有关详细信息，请参见第4.2节。0图模型在某些方面模拟了现实世界网络[2,23]。我们还使用偏斜分布来生成观点。我们使用AaronClauset的randht.m文件[9]根据给定的斜率生成观点。我们通过除以最大观察值来将观点归一化到[0,1]范围内（即总有一个观点为1的节点）。0机器规格。所有实验都在一台配有1.7 GHz英特尔Corei7处理器和8GB主存储器的笔记本电脑上运行。0代码。我们的代码是用Matlab编写的。我们的代码可以在https://github.com/tsourolampis/polarization-disagreement上公开获得。04.2实验结果0合成实验。表2显示了我们在学习最佳图拓扑（即解决问题1）方面的结果，这些结果是在5个实验中对各种固有观点向量进行平均的。每一行对应于根据幂律分布（斜率分别为1.5、2和2.5）对100个固有观点向量进行采样。列 L �0显示了我们优化算法实现的目