文摘

问题意见扩散研究了几十年。迄今为止没有实证方法模型的交流和形成人群的意见在选举中由于两个原因。首先,不同于信息或流感的传播,个人有自己的内在态度提前选举候选人。第二,意见通常简单地假定单个值在大多数扩散模型。然而,在这种情况下,一个意见应该代表向多个候选人的偏好。以前做的模型从而不能直观地解释这样的场景。这项工作是设计一个扩散模型能够管理上述场景。证明我们的模型的实用性,我们模拟扩散网络上建立基于公开的书目数据集。我们比较该模型与其他知名独立级联模型等。事实证明,我们的模型优于其他模型。 We additionally investigate electoral issues with our model simulator.

1。介绍

巨大成功的病毒式营销现在清楚地表明,熟人确实极大地影响人们采用一种新的或不同的意见。这其中牵扯到的人,在某种程度上,试图植物他们内在的想法,意见,或通过交换意见偏好在别人的思想在不同的情况下。一个有趣的和电信业场景是选举。选举在现代世界是一个重要的机制,聚集群众的意见和共同决策用于各种各样的目的。人们分享想法,甚至试图说服别人接受他们的态度在选举季节。

Facebook等社交媒体被广泛使用,它很方便人们表现自己。社交媒体曝光赠款人迄今为止广泛发表他们的观点。社交媒体极加速和促进这种opinion-exchange个体之间的交互。意见交流,内在的意见一个优柔寡断的人最终会被同化的决定的。然后达成共识或舆论出现。

研究方面,了解人类的进步谈判利益现实世界的应用程序。例如,社会学家会怀疑到什么程度的意见交换朋友间相互影响的观点。活动公司询问如何促进预算有限的候选人。这些问题不容易回答通过用户研究,特别是当参与者的数量变得巨大。

在社交网络上意见扩散已经研究了几十年。不幸的是,许多以前的模型,如独立级联模型,线性阈值模型,先生/ SIS模型,和热扩散模型,不能管理选举情况直观地由于以下两个原因。首先,人们有自己的内在观点或多或少,没有在上述模型。在这样一种方式,人们不可能作为中立的继电器。人放大他们代表的意见和deamplify他们反对意见。第二,意见可以是多维的,例如,多个选举候选人的观点。大多数扩散模型采用单个值代表意见为简单起见。一个值显然不能直接代表了对多个候选人的看法。我们的目标是设计一个合适的扩散模型,能够管理观点的传播。到目前为止我们还没有看到太多的计算方法与系统和可量化的研究这个问题。

灵感来自现实世界的现象,我们已经意识到一些可取的属性来管理信息扩散如民意调查。属性是高维媒体,输入的依赖,确定性收敛,共识。属性的摘要如下。首先,我们喜欢媒体(代表对候选人偏好)传播在整个过程中作为一个单位向量,因为民主、个人(或节点)在投票有平等的权利。第二,偏好分布应该是最初的内在偏好以及影响邻居们通过社交网络。最后,我们希望传播最终收敛,和一个共同的趋势似乎经过无数交互(1]。在本文中,我们表明,我们的模型是唯一满足现有模型中所有属性。

本文的新颖和贡献可以从几个不同的角度。(1)这个工作战略演示了一个似是而非的回答一系列现实问题的过程。(一)我们先设计一个偏好谈判模型与理论(担保)管理高维信息。我们评估这个模型的质量证明其收敛性和其他几个重要属性。(b)我们进行实验来证明我们的模型在预测的有效性中引用偏好转变,作者通过协作网络。(c)进一步构建扩散仿真框架,我们设计套卫星算法偏好剖面采样、部署和seed-voter选择。(2)我们的案例研究,在实践中,提供了具体的解决现实世界问题的关注。(一)仿真表明,选举结果可以显著受到社会因素的影响。我们发现每个人偏好概要极更改后扩散的偏好。利用肯德尔扩散系数测量之前和之后的相似之处,这通常会导致下面的系数。(b)与模拟,我们另外检查几个著名的投票模式来验证他们的脆弱性买票。其中,Borda数投票模式执行最好的抵抗买票。多数投票是最容易受到操纵。

2。初步

我们回顾以前做过相关工作的信息扩散和选举问题。

2.1。扩散模型

制定扩散模型模拟或预测,研究人员发现底层机制或固有的模式信息扩散现象和利用这些发现的词。

线性阈值模型(LT模型)(2,3)和独立级联模型(简称IC模型)3,4)是最著名的和基本的描述信息传播网络中一步一步。在两个模型的思想的启发下,各种模型提出了更具体的场景之后。

LT模型起初打算描述关闭的过程由于连锁效应的能源电网超载。然后采用概念模拟扩散的信息。在肝移植模型中,节点在网络中能量的容器(信息)和数量进行表示为实际值。每个节点都有一个预定承载能力,最初并没有能量。一旦模拟所得,某些节点被分配为早期采用者,第一组获得能量(信息),携带能量,进行数量逐步增加。一旦携带能量的总量超过了他们的能力,节点变得活跃(过载)和过度的能量传递给其他链接节点。这将导致功率过载的传播。

操作类似于肝移植模型,集成电路模型进一步简化了信息作为二进制值。节点成为活跃一旦他们收到的信息从链接的邻居。没有预定的集成电路模型中节点的能力。相反,每条边与一个实数表示的概率成功的信息传递。在扩散过程中,积极通过边缘节点不断尝试发送信息,直到所有邻居变得活跃有关。

肯普et al。(2003)3]通用集成电路模型通过引入通用级联模型。Gruhl et al。(2004)5和Leskovec et al . (2006)6)提出了生成模型模拟的博客文章生成基于集成电路模型。这些模型假设节点可以将从活动到活动给予一定概率进行级联。LT模型和集成电路模型的基础上,齐藤et al。(2010)7)提出了异步线性阈值模型和异步独立级联模型。

另一个有影响力的研究,成功的PageRank算法,把传播过程在一个明确的递归的数学形式。热扩散(8,9]是一种物理现象描述热量从高温岗位流向低温位置。灵感来自于热扩散,Ma et al。(2008)8)提出了一个模型来分析候选人选择市场推广策略。这个过程是制定 在哪里节点热吗在时间和的导热系数,即热扩散系数。

在传热过程中,每个顶点接收热量从邻国,它类似于我们的模型。主要区别,在下一节中,将详细讨论,热扩散模型缺乏规范化阶段(因为它只考虑一个值)的传播和融合阶段(因为热本身可以扩散后消失,所以没有必要融合热扩散模型)。

受这些以前的作品,我们的模型需要这些方法的长处,即他们关注模仿社会互动等特征形成共识以及他们公司的结构信息传播过程中,混合成一个更加团结的框架,可以用来回答现实问题在介绍中提到的。

2.2。选举问题

1992年,巴尔托迪三世et al。10)首先研究过程的复杂性决定行动的组织者需要添加或删除候选人操纵选举结果(被认为是经典社会选择理论)。然而,他们没有提出任何的选民之间的交互模式。吉伯德[11]和Satterthwaite [12]表明,每次选举方案至少有三个可能的结果是受个人操作。这意味着少数有机会操纵集团决定安全优先的结果。吉伯德Satterthwaite也解决了计算困难的少数人操纵。然而,他们的模型假设的独立选民,不考虑也不讨论其他选民的影响选民的偏好。现有的研究在这个方向主要集中在复杂性和可行性问题,这是非常不同于我们的目标。

刘(2009)(13]试图检查是否偏好分布变化如果政治专家在一个通信网络的数量增加。他们使用一个基于主体的仿真模型。每个代理模型中维护一个二进制值向候选人(而不是实际价值或排名)和简单的传播价值的其他代理在附近的3 * 3的矩阵。

Yoo et al。(2009)14]提出semisupervised重要性传播模型。他们的想法是,在某种程度上,类似于我们的“融合阶段”通过添加原创音乐从邻居获得累计分数。他们的模式和我们的区别在于他们的处理一个值而不是一个矢量,因此他们不执行标准化在候选人分数像我们一样。

选举操纵是一项讨论已久的问题。然而,这些作品的社会因素是缺席的。这里我们把婚姻之间的社会网络分析和选举问题。

3所示。该模型

我们在这里提出的扩散模型挖掘沟通如何影响个人决策。缩写列出论文的其余部分中使用的符号。

3.1。偏好传播模型

我们首先定义一个配置文件的偏好一个人的,这是一个维向量表示的偏好向不同的候选人。的th元素是一个整数表示这个人偏爱的候选人(较小的数字表示更高的排名)。为了便于偏好配置文件的操作,我们翻译成一个向量的分数,尽管使用以下方程: 在哪里。这种转换可以被视为一个规范化的过程首选的候选人不仅得到更高的分数也是所有元素之和等于1。利用每个人的得分向量,我们可以创建一个通过矩阵用偏好矩阵。我们的偏好矩阵表示给定的时间戳由于传播过程开始。

传播的信息在我们的模型中一个又一个的迭代,每个迭代和包括三个阶段:传播,归一化,融合。

在传播阶段,每个节点从传播偏好得分向量邻近的节点。来描述这些操作在数学上,我们定义一个向前转移矩阵这样的乘法和代表了每个节点获得的分数这个阶段后所有的邻居。我们表示了。

我们假设网络中边的方向揭示影响的方向。因此,,在那里是一个对角矩阵,对角中的每个节点度的倒数和的邻接矩阵。请注意,相同的转发矩阵随机漫步算法。唯一的区别是,在一个随机游走算法由一个矩阵乘以一个向量,而不是。

在,每一行代表了邻居的累积分数对每位候选人的偏好。不像每一行的元素不加起来。确保每个人都有平等的影响而投票,我们每一行的正常化所以它的元素添加到一个。因此,在第二阶段中,乘以一个对角矩阵归一化,每个元素的对角线等于所有元素的和在相应的行吗。第二阶段后,我们将获得一个新的评分矩阵。

我们的传播模型的主要区别和电/热扩散模型(见部分2更多细节)在于传播媒体的内在差异。电或热流从一个地方到另一个(也就是说,一个从节点到节点意味着材料中不存在了)。相比之下,意见不消失后传播(即,倾向的候选人也不消失,即使把他或她的意见)。因此,我们添加一个第三阶段包括融合模型,集成了个人的见解与意见来自邻国。

在融合阶段,我们引入一个参数为每个单独的:敏感率,一个实数表示一个人是多么容易受到别人的影响。给定一个敏感性参数对每个人来说,我们可以创建一个敏感矩阵,一个对角矩阵的每个在对角线的价值。如果等于单位矩阵,这意味着所有人都是和高度敏感,应该相当于其邻居的意见吗。在另一侧,如果等于零矩阵,这意味着所有的个体都不透水,呢应该是相同的。因此,传播一个迭代后,偏好得分矩阵可以表示为

请注意,我们假设不随时间变化,也没有吗(这是只依赖于拓扑)。有趣的是,乍一看可能假设之一改变迭代;它实际上并没有。因为在每一列的总和= 1,所有候选人的分数总是规范化,不难证明 这只取决于。因此,我们可以重写作为,在那里是一个长期有效的矩阵,这成为一个重要的功能的证明收敛下一节。

上述结论是一个迭代的传播。在接下来的迭代中,成为初始偏好得分个人和相同的过程可以获得新一轮的传播执行结果。算法1是我们的算法模型。

3.2。证明了收敛性和共识

在本节中,我们展示了我们方案的收敛性质。得分矩阵变得足够数量的传播后不变。此外,我们表明,给定一定的条件下聚合中的所有行得分矩阵是相同的。换句话说,在一个社区最终将达成共识通过信息传播模型。

让表示所有的总体偏好传播操作三个阶段明确了在上一节中, 为即将到来的减税和借款提供直观的属性的结果从部分3.1,我们首先指出的相似性以及之间的差异和网页级别矩阵。首先,实体作用于实际上是一个矩阵组成的概率,而不是一个简单的向量的向量的概率。因此,列的不加起来1(只有行),因此这不是一个随机矩阵。此外,社会人际关系网络本质上是更本地化的万维网相比,和,因此,有利的正定财产所享有的不一定适用呢。说,这些复杂性,而毫无疑问,复杂的理论治疗我们的算法,实际上是一种自然的表现丰富的增加我们的目标研究hand-social网络。

我们开始收敛的演绎通过征集Perron-Frobenius定理(15)即一个不可约,非循环矩阵有一个特征值,严格大于其他人。假设所诱导的图,,是强连通的,权重矩阵条目小于一个但不是所有0,不可约和无环,因此适用于Perron-Frobenius定理。我们表示占主导地位的真正的积极特征值通过。带着这个事实,我们可以变换进入约旦标准型 主要的块是一个矩阵和其他严格的对应于他们的小的特征值。通过矩阵乘法规则,所带来的影响在可以分析一个接一个对吗的列向量不失一般性,我们将继续我们的证据被关注的收敛性的列向量,我们用小写字母表示。分解成的总和的特征向量,,我们获得的时间演化的一般形式, 在哪里 上面的显示收敛于零的时候大,因此收敛于。获得一种直觉这收敛的速度,我们求助于特殊情况敏感的比率是相同的;也就是说,是一个标量。在这种情况下,我们再次申请Perron-Frobenius定理我们再次获得约旦的形式 然而,请注意,因为它不需要无环,它是严格大于另一个。现在,我们发现使用这个基础等于

由于约旦标准型是独一无二的,我们获得。从这个结果,我们确认的时候,最微不足道的对角线的情况,为退化方法1,几何与收敛速度。

我们现在离最后一步的证明收敛。回忆,,一旦建立了,是收敛的。为了证明这一点,我们利用Collatz-Wielandt定理使下面的公式:,在那里和。

我们首先声称的上界是1。为了证明这一点,我们假设相反,这意味着存在这样。这意味着以下方程: 请注意,。因此,上述方程可以安排到列表 然而,通过指示的下标和记住是一个非负矩阵,上述方程不会持有之一: 这证明断言。将这一结果与微不足道的观察向量收益率,我们得出这样的结论:。因此,,收敛于。

网络不强连通在线性时间,我们总是可以找到癌问题降低到更小的“源癌”以来网络矩阵的所有其他癌阶石根小于1和它们的元素最终消失。剩下的源癌,因为没有顶点敏感性比率等于1,根据上述结果他们都收敛。净效应是以鲜明的区别个人属于各种癌和其他来源。而源SCC顶点将收敛于他们各自的共同价值观,其他人可能收敛于不同的价值观和作为追随者的调整自己的偏好的加权平均属于来源。图1给出了这类现象的一个例子。让所有节点的初始偏好矩阵图1是 在偏好矩阵中的每一行表示每个节点的偏好为候选人1,2和3,分别。然后经过无数的传播,将成为偏好矩阵 A和B的偏好节点图1候选人1收敛于共同的价值候选人2收敛的共同价值和候选人3收敛于共同的价值。然而,对于节点和,考虑到鳞状细胞癌由他们是两个意见领袖的影响下鳞状细胞癌和他们最终的偏好,而不是结盟共同价值成为首选项的线性组合和。这种组合的具体细节取决于网络的结构。

偏好传播模型模拟这种独特的行为的人,将偏好的向量投射在领先的统一的特征向量表示的平衡。此外,它还试图模仿现实世界的追随者的意见领袖的区别。与它的真实世界,这个过程是完全取决于每个个体的初始偏好和嵌入社会网络的结构。

另一个例子是图所示2、时间偏好的演化由社交网络中的节点展示意见领袖的影响,创造出自己的共识,通过舆论的追随者以级联方式。我们看到意见追随者鳞状细胞癌由节点15到20与各种颜色的深浅的灰色根据其距离两个意见领袖癌由节点1 - 3和4 - 7。我们观察的偏好意见领袖癌1 - 3是追随者癌首先传递给意见来(在10日传播轮),然后随后传递给意见追随者通过努力癌癌12到14来以级联方式。

这个简单的例子表明,强连通源组件形成意见领袖群体,虽然每个追随者节点(即影响。线性组合)周边意见领袖群体的意见。框架模型观察现实世界不太相信人员是如何影响他们遇到的质量意见。

3.3。与其他模型相比

我们在这里讨论一个成功的社会模式的最显著特征是基于共同的观察和信仰,为了对比最特色的我们的模型与先前提出的其他框架。

高维度的媒体。因为个人喜好描述所有可能的候选人的偏好顺序,媒体在一个理想的模式应该表示为有序列表而不是单个值。大部分的传播模型,如线性阈值模型,独立级联模型,或DiffusionRank模型,不幸的是,只有处理二进制或实际价值传播。

拓扑结构和输入依赖的依赖。口碑的主要策略是影响他人的人。现实世界的过程指导的朋友向采用self-preference相同时。国家这种现象,即将离任的说服一个人的理想情况下应该成为self-preference和传入的偏好。一个理想的模型应该考虑网络结构和初始个人偏好。此外,我们希望一个模型将这两个因素的方式尽可能自然,而不是依靠临时停止设计或者仅仅是限制数量的时间节点或个人的交互。

确定性收敛。当然理想模型应该收敛或最终结束,否则很难modeler的解释结果。据我们所知,目前有两种设计达到收敛。第一个,如LT模型和集成电路模型、高度的二进制状态网络中每个节点来确定是否访问。的不活跃的地位意味着还没有访问的节点而活跃的状态意味着节点访问。这样的设计,优先传播活动节点很容易监控。此外,传播在该模型收敛所有的现有节点可以改变状态了。

网页排名算法的成功后,第二受欢迎的方法本质上是将收敛机制模型,以便足够的迭代模型收敛后,产生一个明确的结果。

结果很容易可分析的,收敛模型,可以产生相同的结果,给出了相同初始偏好的节点和网络结构,是首选。

共识。代理达成共识的问题研究了自1970年左右(16,17)与选民模型等仿真模型(1]。莫塞尔等人给出了理论证明可以达成的共识与选民模型(18]。因此一个理想的模型应该能够反映特定的共同特征。特别是,我们观察到这样的一个普遍特征是人们在同一个社区(即。鳞状细胞癌)倾向于使他们充分交流后的偏好。这转化为一个理想的模型应该包含某种同质性在一个组。

看看我们的模型和其他提出框架捕获以上真实世界的社会互动的特点,我们进行了几个实验,记录他们的结果在表1为了便于比较。我们特别选择模型,大多数代表自己的立场,即线性阈值模型,独立级联模型,PageRank模型,和DiffusionRank模型比较。传播媒体注意,因为这些模型不是一个向量的偏好,我们做了以下改进为他们每个人来处理这种情况。LT和集成电路模型中,我们假设每个顶点最初批准其前举行首选的候选人(nonapproval他人),因此,对于每个候选人,我们可以获得一个种子列表作为输入到LT和集成电路模型。然后执行模型分别对每个候选人,收集他们的结果,和规范化形式每个顶点的最后选择。PageRank和DiffusionRank模型,因为他们可以真正的值作为输入,我们只是执行这些模型分别对每个候选人的偏好列表,然后综合结果是一个向量的实数。

如表所示1,我们看到,我们的模型是唯一的模式,直接对列表进行操作的偏好,而其他模型工作限制性地执行单一的布尔或实际值和分别获得一个联合偏好,而没有考虑候选人的偏好得分的相关性。我们注意到所有的模型提供收敛的结果。此外,由于集成电路模型的随机组件,它不提供可重复的最终结果的偏好。

检查这些模型是否能给一种共识的节点属于一个强连通网络,我们执行所有的模型在一个强连通图,直到他们自然停止或收敛。事实证明,除了我们的模型,没有显示出最终的输出参数之间达成共识。注意,我们的模型并不产生共识non-SCC组件。

这些模型是否考虑初始偏好持有的节点,我们给所有有六个不同初始偏好模型,看看他们给六个不同的结果。毫不奇怪,PageRank模型返回相同的结果无论输入,表明它只考虑网络的结构,但忽略了初始偏好由每个节点或个人持有。总之,我们的模型是唯一的框架,它支持所有五个标准设定的观察从现实世界的社交网络。

4所示。实验

在本节中,我们比较我们的模型和著名的扩散模型来评估性能。我们检查是否所有上述算法,包括我们,可以捕获在社交网络过渡到一定程度上的偏好。进行这样的验证,我们要求等信息网络结构和节点的偏好。

4.1。偏好数据

科学研究论文的引文含蓄地揭示作者的研究兴趣。换句话说,我们相信行为如引用或提交期刊或会议将是一个指标,作者的利益。利用这一事实,我们可以推断出研究者的偏好从相应的频繁引用会议和期刊。我们进一步意识到一个作者的偏好可能会影响其他的合作者。尤其正确advisor-student关系以来,顾问和学生通常互相影响的研究兴趣。因此,我们设计了一个实验模型研究人员的偏好是如何受到合作者的影响。

我们使用KDD Cup 2003 ArXiv HEP-TH(高能物理理论)引文网络(19)与相应的元信息作为评价数据集。从1992年到2003年这个数据集包含引用。我们选择16期刊拥有大多数报纸作为首选项列出候选人构建和构建每年首选项列出所有作者。偏好列表包含相应的期刊的引用计数在一年。因此,对于每一个作者,我们有12列出代表他们的偏好。

我们之所以使用引用而不是作者是出版物的出版意味着不仅偏好,而且能力。相当现在的利益,我们使用引用。此外,我们从这个数据集构建协作网络作为底层社会偏好扩散骨干。容易感知利益的变化,我们删除作者少于5出版物的数据集,从而导致2683个节点的网络。

4.2。模型比较

因为我们已经有了所有需要的信息包括网络结构和偏好转变,下一步是研究扩散模型预测偏好过渡好。我们假设一个好的扩散模型可以捕捉的发展通过合作作者的研究兴趣。为此,我们最初设置节点根据年实际数据的偏好然后比较预测结果与实际的偏好。以下问题中提到的实验。

高维度的媒体。代表的顺序对所有候选人的偏好,媒体在一个理想的模式应该是有序列表,而不是单个值。尽管如此,大多数知名的扩散模型,如LT、IC、和DiffusionRank,只有把媒体作为布尔或实数。相比之下,我们在问题,利用这些模型执行独立对每个候选人。我们评估候选人排名基于每个独立的扩散结果。

决定论的最终状态。除了集成电路模型,所有上述模型的结果是确定的。因为参数(即。,diffusion probability) in IC model is a nondeterministic factor, we execute the experiment时间和平均结果。

初始化。因为媒体在LT和集成电路模型不是本地对高维度,我们单独处理每个候选人的传播。这意味着,在我们的实验中,前1%的活跃模式作者特定的出版商最初设置活跃在LT和集成电路模型,而其余的出版商不活跃。我们进一步的扩散概率设置每条边,在那里源节点的度在集成电路模型。在肝移植模型中,我们分配与相同的重量和节点相同的阈值。LT和集成电路的参数然后调谐找到最优的结果。传播过程中执行多次与不同的阈值和平均性能。对于DiffusionRank模型,我们使用的作者建议的参数设置9]。

4.3。实验结果

扩散模型是评价通过比较他们对偏好的预测在1997年,1998年和1999年,在使用真正的偏好从1993年到1996年期间为初始状态。测量之间的相似性预测和实际结果,我们采用肯德尔的τ系数(20.)和Jaccard系数。我们分别测量每个作者的相似,网络中的每个节点,然后平均绩效指标。因为肯德尔的τ系数不是定义良好的平局,我们手动设置肯德尔的τ得分0时把所有16个出版商。此外,我们计算Jaccard系数执行上面3得分最高的出版商。

首先,为了了解之间的对应关系的迭代和近年来的变化,我们在每个模型中执行一个迭代传播,然后比较结果与地面真理在1997年,1998年和1999年,分别。我们也尝试不同的敏感率在我们的模型意味着作者坚持他们自己的偏好不考虑效果的邻居。表2显示了结果,我们找到很合适的一个迭代的时期。结果表明,我们的模型一直优于第二DiffusionRank最佳模型,无论使用敏感的比率,只要它不是。

其次,我们执行多轮扩散算法,比较它们与1997 - 1999年的地面实况。表3显示了平均分数为1997,1998和1999。注意,LT和集成电路模型停止当没有可能激活(视为一个回合),这意味着作者并不影响他们的邻居第一轮完成后。表2和3另外显示不透水的偏好()达到性能类似于最好的结果,这可能揭示了自然慢慢改变。然而,结果表明,我们的模型可以忠实地捕捉社会影响的特征,即使作者的利益变化缓慢。

5。类似的模拟框架选举行为

基于偏好的谈判模型,我们实现一个模拟框架,如图4,给予我们分析社会对选举的影响。

5.1。系统架构

选民们拥有自己的偏好配置文件中的每个候选人选举早期阶段。忠实的模拟应该产生偏好配置文件,类似于实际情况。因此,我们生产资料满足一定的分布根据收集到的数据从历史的选举。

虽然我们选民的偏好数据,但不幸的是,没有信息告诉我们的选民之间的关系。为了解决这一问题,我们提出几个合理的场景部署概要文件在一个给定的社交网络。因为人们通常成为朋友由于类似的品味和思想,资料不应随机分布。我们设计几种合理的方式分配偏好配置文件在一个社交网络。

一旦选择概要文件被分配到每个节点,系统开始执行优先谈判模型。网络中的节点开始说服别人和被说服。没有必要为一个仿真运行直到收敛,因为在现实世界中存在一些选举,留下足够的时间来谈判,辩论,或者交换意见之前投票。

最后,因为在每一个阶段有几个参数我们可以调整,我们设计了一个用户界面,允许简单的执行实验(见图3)。

5.2。偏好形象代

在偏好概要文件生成阶段,我们创建的偏好从OpenSTV概要文件获得选举基于历史数据,在线投票记录数据库。我们选择使用“澳大利亚墨尔本维多利亚市议会2008 -市长领导团队”的数据集,因为它是迄今为止我们发现的最完整的数据集。这个数据集被记录在11月29日,2008年,57961年和11名候选人的选票大小。它由首选项列出的所有选民。偏好列表排序候选人名单揭示这个特殊的偏好顺序投票。

我们提出一个ranking-preserved抽样法来产生偏好资料基于历史数据,目的是保护每个候选人的排名。鉴于我们的历史数据,我们首先学习矩阵,在那里等于候选人的总数。的th元素编码的概率th地位排名属于候选人根据历史数据集,。每一列的收益率的概率分布为每个给定级别的候选人。鉴于样品,我们可以反复候选人在每个等级(从高到低)基于分布(禁止的自然限制在不同的位置在一个相同的候选人投票)。

5.3。偏好部署

正如老话所说“鸟以群分,我们假定类似偏好配置文件的人有更大的可能性被网络中互相接近。下面是三个算法来实现这样的想法。

贪婪的部署。它可以实现,首先随机选择一个概要文件,将它分配给社交网络中的一个节点;然后我们将最相似的未赋值的配置文件分配给他们的邻居。为每个未赋值的节点,然后迭代算法分配一个概要文件,是最类似于其邻国。相似度来衡量,我们利用常用的假象系数:

以社区为基础的部署。我们的基本想法是将社交网络社区与集群偏好的配置文件。我们第一次进行社区检测算法识别社区在一个社交网络(在实验中,我们运用21]),组织社区并确定社区的数量自动的基于模块化的最大化。接下来,我们应用一个聚类算法(在这个实验中,我们使用——)组偏好配置文件集群基于肯德尔相似点。

在最后一步中,我们为每个节点分配概要文件。主要的思想是,分配中的每个概要文件最大的集群中的每个节点最大的社区。然而,这不是一个简单的任务,因为th社区和相应的集群可能有不同的大小。在这里,我们提出一个方法来调整集群大小相匹配的社区。为此,我们第一套社区和他们的集群通过各自的大小。然后从最大的社会最小的,我们比较的大小社区与集群。当社区的大小是一样的th集群,我们这个概要文件随机分配到集群中的一个节点在社区。当集群规模比较小,我们添加这个集群外的未赋值的点但最接近集群中心到集群,直到它的大小匹配的大小社区。当集群较大,相比之下,我们的点从集群中移除最远的距离最近的中心和加入他们未赋值的邻居集群。这样迭代会逐渐将概要文件分配给节点和保证节点在同一个社区也有类似的资料。一个示例见图5和伪代码中列出的算法2。

种族隔离的部署。我们的想法是从谢林的隔离模式的设置22:黑人和白人可能不介意,甚至喜欢,彼此的存在,但人们将如果他们是少数。在一开始,我们随机部署概要文件。然后,在每个迭代中,只有不到30%的节点邻居与积极的假象相似度值将被选中,他们偏好配置文件将被打乱。在这个实验中,1000次迭代执行。

5.4。选择谈判

一旦配置文件和社区已经被分配,框架执行核心谈判模型网络的偏好。有两个参数,可以有一些影响过程:谈判的迭代比矩阵和敏感。控制谈判迭代在选民把选票。在下面的实验中,我们设置。

我们设置作为默认为所有选民对于我们的案例研究。建议在我们的证明,如果是一个常数矩阵,那么由此产生的聚合偏好矩阵是冷漠不管什么是(只有控制收敛的速度)。

6。案例研究

在本节中,我们回答两个问题的基础上,提出了仿真框架。(1)到什么程度的谈判进程在一个社交网络影响选举结果?(2)在众所周知的投票模式,Borda数,批准,多元化,这是最容易买票(即。,最容易被操纵)?

为了构造模拟中,我们使用三个合作网络(ca-GrQc包含5242个节点和2890边,ca-HepPh包含12008个节点和237010边,和ca-HepTh包含9877个节点和51971边缘)作为底层社会网络数据集。一旦谈判进程结束,偏好得分向量将检查确定候选人的最终等级使用不同的投票模式:Borda数,批准和多元化23]。我们在所有三个合理的部署进行实验提出了部分5。3。理想情况下,我们希望在所有三个部署方法仿真可以产生相似的结论,这将因此为用户提供更高的信心的结果。

Borda数决定最后排名的候选人给每位候选人一定数量的点对应的位置排名由每个选民。一旦所有的选票都算候选人可以通过他们的总排名点。对于每一个投票,排名第一的候选人将会收到点,第二个点,等等。

的排名批准和多元化模式类似于Borda数决定。唯一的区别在三个投票模式的定义点给每个候选人。在批准的投票模式,顶部候选人在每个投票将每接收一个点,而其余的将不会收到任何点。在多数的投票模式,只有候选人收到一个点。

6.1。谈判的有效性

第一个问题是是否social-network-based谈判过程可以显著影响选举结果。量化变化在选民的偏好通过谈判,我们计算平均肯德尔系数之间的偏好订单之前和之后的每一个谈判。

如图6无论使用哪种方法部署,肯德尔的平均水平系数普遍降低,当我们进入更深的轮谈判。斜率是最大一开始,揭示这一事实谈判到达峰值的影响开始,逐步下降,这与真实世界的经验。最终,肯德尔值降低到0.5以下,这意味着谈判通过社交网络可以显著改变选举结果。

6.2。脆弱性买票

本节讨论关于选举的一个关键问题:如果一个组织可以通过操纵提高候选人的投票计数某些种子节点的偏好配置文件(轻蔑地,我们可以称之为“贿选”)。我们定义一个成功买票选民为“提高目标候选人的偏好得分略高于所需的分数获得选民的投票。“例如,如果每个选民可以投3票,然后买方将试图提高其分数略高于第三位候选人。量化这种操纵成本,我们将它定义为分数操纵之前和之后的区别。买票之前必须重整后的得分向量进一步计算过程。

丢弃的影响谈判,它直观的假设是最好的促销策略是针对选民的成本是最小的。在这样的攻击,这投票模式是最容易买票吗?这个答案可以推断从图7,那里的设在代表预算而度过的设在代表一个给定的秩晋升候选人。请注意,价值就越高代表越有利,候选人必须移动到较低的位置才能当选。结果表明,无论部署,Borda数模式始终需要更多的预算推进目标候选人,而多元化模式是最容易买票,因为它通常需要更少的预算候选人提前到更高的等级。

7所示。结论

分析社交网络在群决策结果的影响是一个困难的问题,因为这既昂贵又耗时进行用户研究来收集人们的私人偏好。事实上,通过社会传播特别偏好的变化,我们最关心的,据我们所知,这是首次研究不仅提供了理论分析也是这个问题的实证依据。这项研究提供了一个示例,如何执行这类研究通过利用算法和有限的数据模型设计,理论依据,和计算机模拟。

我们的另一个重要贡献是我们提供另一种评估计划和数据来验证一个偏好传播模型。承认缺乏现实世界的数据来评估选民的偏好可以改变通过社会扩散,我们想出了一个新奇的想法确定一个公开可用的参考书目数据集评估研究人员逐渐改变他们根据他们的合作者的影响研究领域。我们的评估计划开辟了新的可能性,允许研究人员优先扩散问题能够评估他们的模型不需要确定一个高度私人选民的偏好数据集。

缩写

:	个人
:	候选人
:	许多个人
:	数量的候选人
:	偏好向量的个人概要文件
:	个人偏好得分向量
:	偏好得分矩阵的大小
:	社交网络层。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作是由美国国家科学委员会,国立台湾大学,和英特尔公司在授予nsc101 - 2911 - 002 - 001, nsc101 - 2628 - e - 002 - 028 - my2 NTU102R7501。