AAAI 2017：华沙大学：策略社交网络分析

你和“懂AI”之间，只差了一篇论文

很多读者给芯君后台留言，说看多了相对简单的AI科普和AI方法论，想看点有深度、有厚度、有眼界……以及重口味的专业论文。

为此，在多位AI领域的专家学者的帮助下，我们解读翻译了一组顶会论文。每一篇论文翻译校对完成，芯君和编辑部的老师们都会一起笑到崩溃，当然有的论文我们看得抱头痛哭。

同学们现在看不看得懂没关系，但芯君敢保证，你终有一天会因此爱上一个AI的新世界。

读芯术读者论文交流群，请加小编微信号：zhizhizhuji。等你。

这是读芯术解读的第39篇论文

AAAI 2017 Senior Member Blue Sky

策略社交网络分析

Strategic Social Network Analysis

华沙大学

Universityof Warsaw

【摘要】个人和团体如何保护他们的隐私不受社交网络分析工具的影响？犯罪分子或恐怖组织如何利用这些工具逃避侦查？在何种条件下，这些工具可以成为策略防范？迄今为止，这些基本问题在文献中几乎没有引起注意，因为大多数社交网络分析工具都建立在一个假设之上，即网络中的个人或团体不采取策略规避这些工具。在此基础上，本文提出了一种新的社会网络分析范式，即网络行为主体的策略行为被明确建模。解决这个研究的挑战有各种各样的含义。例如，它可能允许两个个体将他们的关系保密或私有。它也可能允许一个活动团体的成员隐瞒他们的成员关系，甚至向“独裁政权”隐瞒他们团体的存在。此外，它还可以协助安全机构和反恐单位了解秘密组织用来逃避侦查的策略，并提出新的应对策略。

1 引言

社交网络分析(SNA)的许多问题近年来在各种学科包括人工智能和多代理系统(Sabater and Sierra 2002; Nguyen, Kowal- czyk,and Chen 2009)得到了相当大的关注。科学家、开发人员和分析人员都致力于提高各种SNA工具的性能，比如中心度测量(Koschutzki et al. 2005)、团体检测算法(Orman和Labatut 2009)或链路预测算法(Getoor和Diehl 2005)等例子。

不幸的是，虽然这些工具有许多合法的应用程序，但它们也可以用来侵犯隐私，甚至破坏个人和团体的安全。例如，通过分析Facebook的拓扑结构以及一些用户的属性，可以推断其他用户的属性(Mislove et al. 2010)。此外，这种“属性推理攻击”(Zheleva和Getoor 2009)可以在“链路预测攻击”之前增强，该攻击旨在揭示社交网络的拓扑结构中出现的链接，这些链接似乎是丢失的，或者是故意的，或是其他的。

自然而然地，包括严格的法律控制(EU: 2015)、算法解决方案(Kearns et al. 2016)以及参与者能够将其个人信息货币化的市场机制(Lane et al. 2014)都提出了支持隐私和安全的各种对策。然而，它们在实践中很难实施，尤其是在全球范围内。例如，那些通常审查包括社交媒体在内的互联网内容的独裁政权将执行法律保护机制，这是极不可能的。

在此背景下，我们问以下问题：一个社交网络的成员如何有策略的操控他们的在线数据以逃避SNA工具？这个问题的解决可以帮助普通民众更好地保护他们的网络隐私和安全。它还可能帮助活动人士组织避免审查。此外，它还可以协助安全机构和反恐部队了解秘密组织用来逃避侦查的策略。特别是，最近关于秘密组织的发现——尤其是对那些精通技术的ISIS——清楚地表明他们有能力压制当局的反恐努力。已知的ISIS所使用的逃避技术包括改变别名和保持个人资料隐私(Nordrum 2016)使用加密通信平台(如Telegraf (Khayat 2015))和分段从社交媒体上消失的整个团体选择别名再次出现在不同的地方 (Nordrum 2016)。事实上，在爱德华·斯诺登(Edward Snowden)披露了美国情报机构(Scarborough 2014)使用的SNA技术的机密信息后，ISIS的逃避能力显著增加。

不幸的是，我们对这种逃避技术没有足够的了解，而现有的SNA工具也没有内化他们的能力。这是因为大多数SNA工具都是建立在一个假设之上的，即网络中的个人或团体没有策略地规避这些工具。即使是专门为分析隐蔽网络(Perliger and Pedahzur 2011)而设计的更先进的工具，通常也会假定在调查中的网络不受战略操纵的影响。有鉴于此，我们认为目前的文献资料已经到达了一个临界点，人们应该高度重视SNA工具的策略逃避和建立新的策略防范工具。

2新范式

在这一节中，我们概述了社会网络分析中的一个新范式，即网络行为者的战略行为被明确地考虑。因此，它位于社交网络分析和博弈论的交汇处(Maschler、Solan和Zamir2013)。

通常，SNA工具是用来解决特定问题的一种算法。例如，一个链路预测算法，它是一个SNA工具，其目标是根据网络的当前结构来预测，在不久的将来，那个连接最有可能被添加到网络中(Getoor和Diehl2005)。一个链路预测算法也可以用于只有部分网络是可观察到的场景，目标是识别看似缺失，但实际上存在于实际的网络中(liben- nowell和Kleinberg 2007)的边。像其他的SNA工具一样，这种算法并没有考虑到社交网络的成员在试图误导工具时可能采取策略性行动。

相比之下，我们建议将SNA问题构建为策略博弈。为此，我们提出了我们称之为Seaker-Evader博弈(以它的基本形式)，其定义如下：

一组玩家N，包括搜索者(s)，以及逃避者(s)，它们是节点、边和/或任何其他网络实体(例如，子图)。原则上，在我们的模型中可能有多个搜索者，我们假设只有一个搜索者。

对于N内的每个玩家，其可用策略集为Si(纯的或混合的)。例如，逃避者i的策略集可以包含在以下操作中构建的逃避算法：(a)与节点j创建连接(即一个节点的“朋友”)；或(b)切断一个已有的连接(即“删除”一个节点的朋友)。在更复杂的设置中，它可以包括“掩盖”现有连接的真实性质，或隐藏它的某些特性。此外，逃避算法也可以被参数化，在这种情况下，逃避者的策略空间涉及到相应的参数范围。另一方面，搜索者可用的策略集可能包括某些SNA工具(探索者可以从中选择一个，或者可能是任意子集)。这些SNA算法也可以被参数化，在这种情况下，搜索者的策略空间也包括相应的参数范围。最后，策略空间可以让搜索者开发出全新的算法，更好地适应逃避者可用的规避策略。

效用函数的集合(或者，偏好关系)代表了玩家对不同行为选择结果的态度；以及

定义“谁知道什么”的“知识功能”。例如，可以假设，搜索者完全无视逃避者可用的逃避技术。

我们假设，在seeker–evader博弈中，玩家理性地促进他们的偏好，每个人都考虑到其他人的理性行为，然后我们寻求系统的平衡。重要的是，由于上述策略空间的定义，我们的模型的均衡将是：

逃避者的逃避技巧

搜索者的SNA工具

因此，SNA工具(可能调整为规避技术)和规避技术(可能调整到SNA工具)将成为我们模型的均衡。此外，虽然上面的模型被定义为一种非合作的博弈，但它可以直接扩展到包含合作行为，例如，在逃避者之间。

虽然定义上述seeker–evader博弈的变量可以设置在任何星座中，但我们认为模型应该逐步建立，从最简单的到最复杂的。我们建议采取以下步骤：

步骤1：分析针对现有SNA工具的潜在规避技术，假定搜索者不能进行策略性行动，并没有意识到逃避者的潜在逃避努力。

步骤2：对现有SNA工具的潜在规避技术进行分析，假设所有各方都是策略性的，尽管策略空间仅限于基本的规避技术和已知的SNA算法。

步骤3：分析针对现有的和可能的创新的(适应新的设置)SNA工具的潜在规避技术。在这里，假设所有各方都是策略性的，策略空间可以采取更复杂的形式。

就我们所知，我们最近一系列关于规避中心测量、社区检测算法(Wanieket al. 2016a)和链接预测算法(Waniek,Rahwan,andMichalak 2016)的论文(Waniek等人，2016a;2016b)，是第一个可以在第一步分类的文献。在下一节中，我们将详细讨论Waniek等人(2016a)的一些结果。

3样本分析

Waniek等人(2016a)关注以下问题：

个人如何积极地管理他们的社会关系，这样他们就不太可能被中心度测量视为重要节点，但同时，他们也不会失去他们在网络中的影响力?

团体如何主动地管理他们的社会关系，这样他们就不会受到团体检测算法的影响?

关于第一个问题，我们现在简单地描述了模型和一些主要的结果。

Waniek等人的模型可以看到一个退化的seeker-evader博弈。它的定义如下：玩家由无策略的搜索者和有策略的逃避者组成。后者采取联合行动，从三种基本的核心措施：度、亲近度和中介性(Koschutzkiet al. 2005)掩盖了网络的领导者。

图1: (Waniek等人，2016a)的图1。在9/ 11恐怖分子网络上执行两次ROAM以隐藏MohamedAtta，他通常被认为是袭击的罪魁祸首之一(Krebs 2002)。在每个步骤中，实红链接是被算法删除的，而被删除的绿色链接是被添加的。

领导者被定义为具有最高影响力的社会网络的成员。在此，我们考虑了两种已建立的影响力数学模型：独立级联模型IndependentCascade model和线性阈值模型LinearThreshold model (Kempe, Kleinberg, Tardos 2003)。由于它假定搜索者者不知道逃避者所做的任何逃避努力，因此这个博弈是退化的。

由于领导者是最有影响力的，他/她通常会被三种中心度指标(度、亲密度和中介性)排在最前面的节点中。因此，逃避者的目标是重新连接网络，以便减少他们的领袖中心，而不影响领导对网络的影响力 (或者，这个设置可以被解释为之间寻求一个节点在中心地位和影响力之间的平衡)。假定为了实现他们的目标，逃避者可以在没有超出某一预算——允许修改的最大链接数(即允许添加或删除)——的情况下重新连接网络的链接。

Waniek等人证明找到解决上述问题的最优解是NP-hard。然而，他们证明，即使是一个简单的启发式，即注意力只局限于个人的近邻，在实践中也会出奇地有效。他们的启发式，叫做“ROAM”——删除一个，增加很多，具体如下。

给定预算b:

步骤1：删除领袖vL和它的某个邻居vi之间的联系；

步骤2：将vi连接到b- 1节点相连，这些节点是vL的邻居，但不是vi的邻居(如果小于b– 1个邻居，将vi连接到所有这些邻居节点)。

图1展示了在WTC911恐怖网络上的启发式工作。有趣的是，ROAM在网络中可以掩盖MohamedAtta的领导地位；这是通过重新布线的方式实现的——他的联系和他的近邻之间的联系。

Waniek等人实验：

两种真实的网络：(i)负责WTC 911袭击、2002年巴厘岛袭击事件、以及2004年马德里火车爆炸事件的秘密网络；(ii)从SNAP (Leskovec和Mcauley2012)中获得的社交网络匿名碎片：Facebook、Twitter和Google+。

三种众所周知的随机生成的网络:(i)无标度网络即Barabasi-Albert模型；(2)小世界网络即Watts-Strogatz模型；(iii)随机图形即Erdos-Renyi模型。

他们的每一个实验都包括一个网络，一个预算(2，3，4的中一个)，一个领导者，一个影响模型(独立级联模型或线性阈值模型)。被选为领导者的节点是中心排名之和最低的节点(在随机情况下，关系会被一致地打破)。一些实验的结果如图2所示。他们关注的是一个秘密组织(马德里爆炸案)，一个社交网络碎片(Facebook碎片)，以及一个随机生成的网络(使用barabasi-albert模型生成的无标度网络，有100个节点，每个节点有3条边)。前三栏中的次要情节描述了领导者的排名，而在后两栏中则描述了领导者的相对影响价值，与领导者在实施启发式时的原始影响价值相比较。可以看出，ROAM启发式方法在降低领导人的排名方面是有效的，其效率取决于预算的大小。至于影响力，高预算的启发式经常会维持(甚至增加)领导的影响力。

Waniek等人的工作也可以被看作是中心度测量的敏感性分析(Correa,Crnovrsanin和Ma2012)研究的延伸。然而，这些文献的分析通常侧重于随机网络变化的影响，而Waniek等人关注的是在本质上是策略性的改变。

4 相关工作

图2:(来自（Wanieket al, 2016a）的图3) 执行ROAM多次，连续时间，其中x轴表示执行次数。这些子图显示了源节点的排名(根据不同的中心度量)，以及它对马德里攻击网络的影响值(根据不同的影响模型)的相对变化(根据不同的影响模型)，50个无标度网络，以及一个中等大小的Facebook分片网络(333个节点，5038条边)。预算b的大小是23 4。

各种各样已经确立的研究主题主要定位在社交网络分析和博弈论的交接面上。其中一个例子就是关于内生网络的经济文献(Jackson2005)。另一个是关于社交网络的机制设计的文献(Singh,Jain，Kankanhalli 2011)。此外，有关网络网络威胁的文献(如Sybil攻击、Danezis和Mittal2009，以及链路重构攻击，Fire et al. 2012)通常都假设一些参与者的策略行为。博弈论也被用作某些SNA算法如团体检测算法(Chenet al . 2010; McSweeney,Mehrotra and Oh 2014)或博弈论中心度测量(Grofmanand Owen 1982; Michalak et al . 2013; Szczepaiiski et al. 2016)。虽然如此，我们认为，我们的建议明确彻底地在社交网络分析中考虑了参与者的策略性行为，扩展了当前最新技术水平。

自然地，在博弈论文献中有各种各样的模型，我们可以用于建立seeker– evader博弈分析。也许最相关的模式是捉迷藏游戏(Rubinstein et al. 1997,chapman et al. 2014)，其中一方隐藏某些物品，另一方则寻求找到这些物品。还有的相关工作包括认知博弈论(Aumann和Branden-汉堡2016)，试图理解和明确(通常是通过使用认知逻辑)关于“谁知道”的假设，通常隐含在博弈论的设置中。最后，安全博弈论——有M.Tambehe 和他的实验室拥护的丰富研究线 (Fave et al .2015)——也有关，因为它在一个安全上下文还考虑的策略互动。

论文下载链接：

https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14941/13993

留言 点赞 发个朋友圈

我们一起探讨AI落地的最后一公里