链路分析


网络理论中,链路分析 Link Analysis是一种用于评估节点之间关系(连接)的数据分析技术。该技术可以鉴别各种类型节点(对象)之间的关系,包括组织、人和金融交易。链路分析已被应用于诸多领域,如打击犯罪活动(如欺诈侦查、反恐和情报)、计算机安全分析、搜索引擎优化、市场调查、医学研究和艺术。


知识发现

知识发现 Knowledge Discovery,是指不断地识别、分析和可视化数据中的内在模式,这是一个持续迭代和交互的过程。[1]网络分析、链路分析和社会网络分析都是知识发现的方法,它们都是属于先验方法。大多数知识发现方法遵循以下几个步骤(在最高级别):[2]

  1. 数据处理
  2. 数据转换
  3. 数据分析
  4. 数据可视化

数据的收集和处理需要访问数据,但此过程存在一些固有的问题,包括信息超载和数据错误等。在数据被收集后,它将转换成一种人和计算机分析程序都能有效使用的格式。之后基于数据,可使用计算机生成的或人工操作的可视化工具进行作图(如网络图)。目前有几种算法可以帮助人类进行数据分析-迪杰斯特拉算法 Dijkstra’s algorithm,广度优先搜索 Breadth-First Search和深度优先搜索 Depth-First Search。

链路分析主要通过可视化方法(网络图、关联矩阵)分析节点之间的关系。这里有一个基于犯罪侦查绘制网图的例子:[3]


关系/网络 数据来源
1.信任 嫌疑人在家庭、社区、学校、军队、俱乐部或组织中已有的关系;公开信息及法庭纪录;只能在嫌疑人本国使用的数据。
2.任务 电话、电子邮件、聊天室、即时消息、网站访问的日志和记录;出入境纪录;人工智能: 会议和出席公共活动的观察报告。
3.资金和资源 银行账户和汇款记录;信用卡使用地点及使用习惯;以前的法庭记录。人工智能: 访问其他银行资源(如 Hawala)的观察报告。
4.策略与目标 网站;由快递公司递送的视频和加密光盘;出入境纪录;人工智能: 会议和出席公共活动的观察报告。

链路分析主要有3个作用:[4]

  1. 在数据中寻找已知兴趣模式的匹配;
  2. 发现与已知模式不相符的异常数据;
  3. 发现新的兴趣模式(社会网络分析、数据挖掘)。


历史

生成缩略图出错:无法找到文件
图1:关联矩阵

Klerks把链路分析工具分为三代。[5]第一代是由哈珀 Harper和哈里斯 Harris在1975年引入的阿纳卡帕图 Anacpapa Chart。[6]这种方法需要一个领域专家来查看数据文件,通过构造一个关联矩阵来识别关联,然后创建一个用于可视化的链路图,最后通过分析网络图来识别兴趣模式。这种方法需要广泛的领域知识,且因要审查大量数据,所以非常耗时。

除了关联矩阵外,活动矩阵也可用于生成对执法具有实用和使用价值的可操作的信息。正如这个术语可能暗示的那样,活动矩阵关注的是人们基于地点的行动和活动。而关联矩阵关注的是人,组织和/或属性之间的关系。这两类矩阵之间的区别虽然很小,但就完成或提供的数据来看,这些区别还是很重要的。[7][8][9][10]

第二代工具包括基于图形的自动分析工具,如 IBM i2 Analyst’s Notebook、Netmap、ClueMaker和Watson。在手动创建关联矩阵的情况下,这些工具提供了自动构建和更新链路图表的能力。然而,对结果图表的分析仍然需要在该领域具有广泛知识的专家。

第三代链路分析工具(例如DataWalk)可以自动显示数据集中元素之间的链路,然后可以在此基础上进一步探索或手动更新、。


应用

  • 联邦调查局暴力刑事逮捕程序
  • 爱荷华州性犯罪分析系统
  • 明尼苏达州性犯罪分析系统
  • 华盛顿州凶杀案调查追踪系统(HITS)[11]
  • 纽约州凶杀案调查和线索追踪系统
  • 新泽西州凶杀案评估与测评跟踪系统(HEAT)[12]
  • 宾夕法尼亚州ATAC程序
  • 暴力犯罪联系分析系统[13]


链路分析的问题

信息过载

由于大量数据和信息以电子形式存储,用户可能会面临拥有多种不相关的信息来源却不知如何分析的难题。数据分析技术的使用可以帮助有效和高效地利用数据。帕尔希卡尔 Palshikar将数据分析技术分为两大类(统计模型、时间序列分析、聚类分类、异常检测匹配算法)和人工智能(AI)技术(数据挖掘、专家系统、模式识别、机器学习技术、神经网络)。[14]

博尔顿 Bolton和汉德 Hand将统计数据分析定义为有监督或无监督的方法。[15]监督式学习方法 Supervised Learning Methods要求在系统中有明确的规则来指出什么是预期行为,什么是意外行为。非监督式学习方法 Unsupervised Learning Methods在审视数据时,通过将数据与正常值的比较,来发现统计异常值。监督式学习方法能处理的场景是有限的,因为这种方法需要基于以前的模式建立训练规则。非监督式学习方法可以检测更广泛的问题。但是,如果数据的行为规范没有很好的建立或被机器理解,可能会导致较高的误报率。

数据本身存在固有的问题,包括完整性(或缺失性)和持续的改变。数据可能包含“由于收集或处理不当,以及试图欺骗或隐瞒其行为而造成的遗漏和委托错误”。 [4] Sparrow[16]强调了数据分析中三个主要的问题,不完整性(数据或链路缺失的必然性)、模糊边界(边界确定的主观性)和动态变化(数据的持续变化性)。[3]

一旦数据转换成可用的格式,就会出现开放结构和交叉引用问题。魏斯曼 Waismann将开放结构 Open Texture定义为在不同语境中使用经验词汇时不可避免的语义不确定性。[17]当试图从多个数据源搜索和交叉引用数据时,术语含义的不确定性带来了问题。[18]

目前,解决数据分析中这些问题的主要方法是依赖专家的领域知识。如此进行链路分析是非常耗时和昂贵的,并且无法排除其自身固有的问题。麦格拉斯 McGrath 等人得出结论:网络图的分布和表示方式对用户的“对存在在网络中群体的感知”有重大影响。[19] 即使是领域内的专家也可能得出不同的结论,因为他们的分析可能是很主观的。


检控与防止罪案

目前,链路分析技术主要用于经营,因为回顾历史数据以期从中获得模式,要比预测未来的行动容易得多。

克雷布斯 Krebs基于袭击后的详细公开资料进行绘图,展示了与9月11日袭击事件的19名劫机者有关的恐怖分子关系网的关联矩阵和链路图。[3]即使有后见之明的优势,以及关于人员、地点和交易的公开可用信息,做出的结果图很明显仍然缺少数据。

另外,皮卡雷利 Picarelli认为,使用链路分析技术可以用来查明并有可能防止奥姆真理教的非法活动。[20]“我们必须小心‘牵连犯罪’。与恐怖分子有联系并不能证明有罪——但确实应该进行调查。”[3]如何在审查潜在敏感数据以防止尚未发生的犯罪或非法活动时不违背合理依据、隐私权和结社自由等法律概念将会变得很困难。


拟议解决方案

有四类拟议的链路分析解决方案:[21]

  1. 基于启发式的
  2. 基于模板的
  3. 基于相似性的
  4. 方法

基于启发式的工具利用结构化数据从专家知识中提取决策规则。基于模板的工具使用自然语言处理 Natural Language Processing从非结构化数据中提取与预定义模板匹配的具体信息。基于相似度的方法使用加权评分来比较属性和识别潜在的链路。统计方法基于词汇统计识别潜在的链路。


犯罪网探险家

J.J.Xu和H.Chen提出了一个自动化网络分析和可视化的框架,叫做 CrimeNet Explorer。[22] 这一框架包括以下内容:

  • 通过概念空间方法创建网络,该方法使用“共现网络”来衡量两个单词或短语在同一文档中出现的频率。两个单词或短语在一起出现的频率越高,它们关联的可能性就越大。[22]
  • 网络分区通过“根据关系强度的分层聚类,将网络划分为子组”而实现。[22]
  • 通过“三种中心性度量(度中心性,中介中心性和接近中心性)来识别给定子集中的中心成员”进行结构分析。CrimeNet Explorer使用迪杰斯特拉最短路径算法 Dijkstra’s shortest-path algorithm来计算从单个节点到子组中所有其他节点的中介数和紧密程度。
  • 使用托格森的度量多维标度(MDS)算法进行网络可视化。

参考文献

  1. Inc., The Tor Project. "Tor Project: Overview".
  2. Ahonen, H., Features of Knowledge Discovery Systems.
  3. 3.0 3.1 3.2 3.3 Krebs, V. E. 2001, Mapping networks of terrorist cells, Connections 24, 43–52.
  4. Klerks, P. (2001). "The network paradigm applied to criminal organizations: Theoretical nitpicking or a relevant doctrine for investigators? Recent developments in the Netherlands". Connections. 24: 53–65. CiteSeerX 10.1.1.129.4720.
  5. Harper and Harris, The Analysis of Criminal Intelligence, Human Factors and Ergonomics Society Annual Meeting Proceedings, 19(2), 1975, pp. 232-238.
  6. Pike, John. "FMI 3-07.22 Appendix F Intelligence Analysis Tools and Indicators".
  7. Social Network Analysis and Other Analytical Tools
  8. MSFC, Rebecca Whitaker (10 July 2009). "Aeronautics Educator Guide - Activity Matrices".
  9. Personality/Activity Matrix
  10. "Archived copy". Archived from the original on 2010-10-21. Retrieved 2010-10-31.{{cite web}}: CS1 maint: archived copy as title (link)
  11. "Archived copy". Archived from the original on 2009-03-25. Retrieved 2010-10-31.{{cite web}}: CS1 maint: archived copy as title (link)
  12. "Archived copy". Archived from the original on 2010-12-02. Retrieved 2010-10-31.{{cite web}}: CS1 maint: archived copy as title (link)
  13. Palshikar, G. K., The Hidden Truth, Intelligent Enterprise, May 2002.
  14. Bolton, R. J. & Hand, D. J., Statistical Fraud Detection: A Review, Statistical Science, 2002, 17(3), pp. 235-255.
  15. Sparrow M.K. 1991. Network Vulnerabilities and Strategic Intelligence in Law Enforcement’, International Journal of Intelligence and Counterintelligence Vol. 5 #3.
  16. Friedrich Waismann, Verifiability (1945), p.2.
  17. Lyons, D., Open Texture and the Possibility of Legal Interpretation (2000).
  18. McGrath, C., Blythe, J., Krackhardt, D., Seeing Groups in Graph Layouts.
  19. Picarelli, J. T., Transnational Threat Indications and Warning: The Utility of Network Analysis, Military and Intelligence Analysis Group.
  20. Schroeder et al., Automated Criminal Link Analysis Based on Domain Knowledge, Journal of the American Society for Information Science and Technology, 58:6 (842), 2007.
  21. 22.0 22.1 22.2 Xu, J.J. & Chen, H., CrimeNet Explorer: A Framework for Criminal Network Knowledge Discovery, ACM Transactions on Information Systems, 23(2), April 2005, pp. 201-226.

外部链接


编者推荐

集智学园:基于图注意网络的链路预测

讲师为谷伟伟,是北京化工大学信息科学与技术学院的讲师。目前的研究领域主要包括复杂网络表征学习、复杂网络理论、中国风险投资网络分析等。曾以第一作者或者共同第一作者发表学术文章4篇。其中关于中国风险投资网络演化的文章于2019年发表在社会网络分析的顶级期刊《Social Networks》上面。

该报告基于中国风险投资的实证数据,建模了风险投资网络的演化过程,揭示了中国风险投资界的小世界及精英俱乐部的性质。


集智学院:数据分析2020

生成缩略图出错:无法找到文件
数据分析2020

该系列课程为北京师范大学系统科学学院樊瑛老师开设的研究生课程《数据分析》课程回放。课程通过理论、案例、实践三方面,介绍统计分析及其在实际领域中的应用,时长为15h5min。

樊瑛 北京师范大学系统科学学院教授、博士生导师。中国系统工程学会副秘书长、常务理事。研究方向为复杂性理论及其在各领域中的应用,目前主要关注复杂网络相关研究,并取得了一系列科研成果。曾获得2009年度教育部新世纪人才、2010年度北京市科学技术奖(三等)以及学校第11届励耘优秀青年教师奖和通鼎研究生教学奖,主讲的《复杂网络分析》课程2019年在中国大学慕课网上线,现已完成2期授课。

CSDN:北冥有一条鱼 链路分析(Link analysis)




本中文词条由Ryan参与编译,WildBoar审校,糖糖编辑,如有问题,欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料,遵守 CC3.0协议。