链路分析

本词条由Ryan初步翻译

In network theory, link analysis is a data-analysis technique used to evaluate relationships (connections) between nodes. Relationships may be identified among various types of nodes (objects), including organizations, people and transactions. Link analysis has been used for investigation of criminal activity (fraud detection, counterterrorism, and intelligence), computer security analysis, search engine optimization, market research, medical research, and art.

In network theory, link analysis is a data-analysis technique used to evaluate relationships (connections) between nodes. Relationships may be identified among various types of nodes (objects), including organizations, people and transactions. Link analysis has been used for investigation of criminal activity (fraud detection, counterterrorism, and intelligence), computer security analysis, search engine optimization, market research, medical research, and art.

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

Knowledge discovery

Knowledge discovery is an iterative and interactive process used to identify, analyze and visualize patterns in data. Network analysis, link analysis and social network analysis are all methods of knowledge discovery, each a corresponding subset of the prior method. Most knowledge discovery methods follow these steps (at the highest level):

Knowledge discovery is an iterative and interactive process used to identify, analyze and visualize patterns in data. Network analysis, link analysis and social network analysis are all methods of knowledge discovery, each a corresponding subset of the prior method. Most knowledge discovery methods follow these steps (at the highest level):

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

1. Data processing

Data processing

数据处理

1. Transformation

Transformation

数据转变

1. Analysis

Analysis

数据分析

1. Visualization

Visualization

数据可视化

Data gathering and processing requires access to data and has several inherent issues, including information overload and data errors. Once data is collected, it will need to be transformed into a format that can be effectively used by both human and computer analyzers. Manual or computer-generated visualizations tools may be mapped from the data, including network charts. Several algorithms exist to help with analysis of data – Dijkstra’s algorithm, breadth-first search, and depth-first search.

Data gathering and processing requires access to data and has several inherent issues, including information overload and data errors. Once data is collected, it will need to be transformed into a format that can be effectively used by both human and computer analyzers. Manual or computer-generated visualizations tools may be mapped from the data, including network charts. Several algorithms exist to help with analysis of data – Dijkstra’s algorithm, breadth-first search, and depth-first search.

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

Link analysis focuses on analysis of relationships among nodes through visualization methods (network charts, association matrix). Here is an example of the relationships that may be mapped for crime investigations:

Link analysis focuses on analysis of relationships among nodes through visualization methods (network charts, association matrix). Here is an example of the relationships that may be mapped for crime investigations:

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

{ | class“ wikitable”

Relationship/Network	Data Sources	Relationship/Network	Data Sources	关系 / 网络! ！数据来源
1. Trust	Prior contacts in family, neighborhood, school, military, club or organization. Public and court records. Data may only be available in suspect's native country.	1. Trust	Prior contacts in family, neighborhood, school, military, club or organization. Public and court records. Data may only be available in suspect's native country.	嫌疑人在家庭、社区、学校、军队、俱乐部或组织中已有的联系。公开信息及法庭纪录。以及只能在嫌疑人本国获得的数据。
2. Task	Logs and records of phone calls, electronic mail, chat rooms, instant messages, Web site visits. Travel records. Human intelligence: observation of meetings and attendance at common events.	2. Task	Logs and records of phone calls, electronic mail, chat rooms, instant messages, Web site visits. Travel records. Human intelligence: observation of meetings and attendance at common events.	| 电话、电子邮件、聊天室、即时消息、网站访问的日志和记录。出入境纪录。人类智能: 会议评论和公共活动的出席。
3. Money & Resources	Bank account and money transfer records. Pattern and location of credit card use. Prior court records. Human intelligence: observation of visits to alternate banking resources such as Hawala.	3. Money & Resources	Bank account and money transfer records. Pattern and location of credit card use. Prior court records. Human intelligence: observation of visits to alternate banking resources such as Hawala.	银行账户和汇款记录。信用卡使用地点及使用习惯。以前的法庭记录。人类智能: 访问其他银行资源的观察，如 Hawala。
4. Strategy & Goals	Web sites. Videos and encrypted disks delivered by courier. Travel records. Human intelligence: observation of meetings and attendance at common events.	4. Strategy & Goals	Web sites. Videos and encrypted disks delivered by courier. Travel records. Human intelligence: observation of meetings and attendance at common events.	网站。由快递公司递送的视频和加密光盘。出入境纪录。人类智能: 会议评论和公共活动的出席。

|}

Link analysis is used for 3 primary purposes:

Link analysis is used for 3 primary purposes:

链接分析主要有3个作用:

1. Find matches in data for known patterns of interest;

Find matches in data for known patterns of interest;

在数据中寻找有意义的已知模式;

1. Find anomalies where known patterns are violated;

Find anomalies where known patterns are violated;

发现与已知模式不符合的异常数据;

1. Discover new patterns of interest (social network analysis, data mining).

Discover new patterns of interest (social network analysis, data mining).

发现有意义的新模式(社会网络分析、数据挖掘)。

History

Klerks categorized link analysis tools into 3 generations. The first generation was introduced in 1975 as the Anacpapa Chart of Harper and Harris. This method requires that a domain expert review data files, identify associations by constructing an association matrix, create a link chart for visualization and finally analyze the network chart to identify patterns of interest. This method requires extensive domain knowledge and is extremely time-consuming when reviewing vast amounts of data.

文件:Association Matrix.png

Association Matrix

Klerks categorized link analysis tools into 3 generations. The first generation was introduced in 1975 as the Anacpapa Chart of Harper and Harris. This method requires that a domain expert review data files, identify associations by constructing an association matrix, create a link chart for visualization and finally analyze the network chart to identify patterns of interest. This method requires extensive domain knowledge and is extremely time-consuming when reviewing vast amounts of data.

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

In addition to the association matrix, the activities matrix can be used to produce actionable information, which has practical value and use to law-enforcement. The activities matrix, as the term might imply, centers on the actions and activities of people with respect to locations. Whereas the association matrix focuses on the relationships between people, organizations, and/or properties. The distinction between these two types of matrices, while minor, is nonetheless significant in terms of the output of the analysis completed or rendered.

In addition to the association matrix, the activities matrix can be used to produce actionable information, which has practical value and use to law-enforcement. The activities matrix, as the term might imply, centers on the actions and activities of people with respect to locations. Whereas the association matrix focuses on the relationships between people, organizations, and/or properties. The distinction between these two types of matrices, while minor, is nonetheless significant in terms of the output of the analysis completed or rendered.

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

Second generation tools consist of automatic graphics-based analysis tools such as IBM i2 Analyst’s Notebook, Netmap, ClueMaker and Watson. These tools offer the ability to automate the construction and updates of the link chart once an association matrix is manually created, however, analysis of the resulting charts and graphs still requires an expert with extensive domain knowledge.

Second generation tools consist of automatic graphics-based analysis tools such as IBM i2 Analyst’s Notebook, Netmap, ClueMaker and Watson. These tools offer the ability to automate the construction and updates of the link chart once an association matrix is manually created, however, analysis of the resulting charts and graphs still requires an expert with extensive domain knowledge.

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

The third generation of link-analysis tools like DataWalk allow the automatic visualization of linkages between elements in a data set, that can then serve as the canvas for further exploration or manual updates.

The third generation of link-analysis tools like DataWalk allow the automatic visualization of linkages between elements in a data set, that can then serve as the canvas for further exploration or manual updates.

像 DataWalk 这样的第三代链接分析工具能自动可视化数据集中元素之间的链接，其结果可允许进一步的人工探索与改进。

Applications

• FBI Violent Criminal Apprehension Program (ViCAP)

联邦调查局暴力刑事逮捕程序

• Iowa State Sex Crimes Analysis System

爱荷华州性犯罪分析系统

• Minnesota State Sex Crimes Analysis System (MIN/SCAP)

明尼苏达州性犯罪分析系统

• Washington State Homicide Investigation Tracking System (HITS)

华盛顿州凶杀案调查追踪系统

• New York State Homicide Investigation & Lead Tracking (HALT)

纽约州凶杀案调查和线索追踪系统

• New Jersey Homicide Evaluation & Assessment Tracking (HEAT)

新泽西州凶杀案评估与测评跟踪系统

• Pennsylvania State ATAC Program.

宾夕法尼亚州ATAC程序

• Violent Crime Linkage Analysis System (ViCLAS)

暴力犯罪联系分析系统

Issues with link analysis

Information overload

With the vast amounts of data and information that are stored electronically, users are confronted with multiple unrelated sources of information available for analysis. Data analysis techniques are required to make effective and efficient use of the data. Palshikar classifies data analysis techniques into two categories – (statistical models, time-series analysis, clustering and classification, matching algorithms to detect anomalies) and artificial intelligence (AI) techniques (data mining, expert systems, pattern recognition, machine learning techniques, neural networks).

With the vast amounts of data and information that are stored electronically, users are confronted with multiple unrelated sources of information available for analysis. Data analysis techniques are required to make effective and efficient use of the data. Palshikar classifies data analysis techniques into two categories – (statistical models, time-series analysis, clustering and classification, matching algorithms to detect anomalies) and artificial intelligence (AI) techniques (data mining, expert systems, pattern recognition, machine learning techniques, neural networks).

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

Bolton & Hand define statistical data analysis as either supervised or unsupervised methods. Supervised learning methods require that rules are defined within the system to establish what is expected or unexpected behavior. Unsupervised learning methods review data in comparison to the norm and detect statistical outliers. Supervised learning methods are limited in the scenarios that can be handled as this method requires that training rules are established based on previous patterns. Unsupervised learning methods can provide detection of broader issues, however, may result in a higher false-positive ratio if the behavioral norm is not well established or understood.

Bolton & Hand define statistical data analysis as either supervised or unsupervised methods. Supervised learning methods require that rules are defined within the system to establish what is expected or unexpected behavior. Unsupervised learning methods review data in comparison to the norm and detect statistical outliers. Supervised learning methods are limited in the scenarios that can be handled as this method requires that training rules are established based on previous patterns. Unsupervised learning methods can provide detection of broader issues, however, may result in a higher false-positive ratio if the behavioral norm is not well established or understood.

Bolton & Hand 将统计数据分析定义为有监督或无监督的方法。监督式学习方法要求在系统中有明确的规则来指出什么是预期行为，什么是意外行为。非监督式学习方法在审视数据时，通过将数据与正常值的比较，来发现统计异常值。监督式学习方法能处理的场景是有限的，因为这种方法需要基于以前的模式建立训练规则。非监督式学习方法可以对更广泛的问题进行检测。但是，如果数据的行为规范没有很好的建立或被机器理解，其结果可能会导致较高的假阳性率（本身不是正常值，但识别为正常值，说明算法预测了“正确”或“有”的判断，但却判断错误了）。

Data itself has inherent issues including integrity (or lack of) and continuous changes. Data may contain “errors of omission and commission because of faulty collection or handling, and when entities are actively attempting to deceive and/or conceal their actions”. Sparrow highlights incompleteness (inevitability of missing data or links), fuzzy boundaries (subjectivity in deciding what to include) and dynamic changes (recognition that data is ever-changing) as the three primary problems with data analysis.

Data itself has inherent issues including integrity (or lack of) and continuous changes. Data may contain “errors of omission and commission because of faulty collection or handling, and when entities are actively attempting to deceive and/or conceal their actions”. Sparrow highlights incompleteness (inevitability of missing data or links), fuzzy boundaries (subjectivity in deciding what to include) and dynamic changes (recognition that data is ever-changing) as the three primary problems with data analysis.

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

Once data is transformed into a usable format, open texture and cross referencing issues may arise. Open texture was defined by Waismann as the unavoidable uncertainty in meaning when empirical terms are used in different contexts. Uncertainty in meaning of terms presents problems when attempting to search and cross reference data from multiple sources.

Once data is transformed into a usable format, open texture and cross referencing issues may arise. Open texture was defined by Waismann as the unavoidable uncertainty in meaning when empirical terms are used in different contexts. Uncertainty in meaning of terms presents problems when attempting to search and cross reference data from multiple sources.

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

The primary method for resolving data analysis issues is reliance on domain knowledge from an expert. This is a very time-consuming and costly method of conducting link analysis and has inherent problems of its own. McGrath et al. conclude that the layout and presentation of a network diagram have a significant impact on the user’s “perceptions of the existence of groups in networks”. Even using domain experts may result in differing conclusions as analysis may be subjective.

The primary method for resolving data analysis issues is reliance on domain knowledge from an expert. This is a very time-consuming and costly method of conducting link analysis and has inherent problems of its own. McGrath et al. conclude that the layout and presentation of a network diagram have a significant impact on the user’s “perceptions of the existence of groups in networks”. Even using domain experts may result in differing conclusions as analysis may be subjective.

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

Prosecution vs. crime prevention

Link analysis techniques have primarily been used for prosecution, as it is far easier to review historical data for patterns than it is to attempt to predict future actions.

Link analysis techniques have primarily been used for prosecution, as it is far easier to review historical data for patterns than it is to attempt to predict future actions.

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

Krebs demonstrated the use of an association matrix and link chart of the terrorist network associated with the 19 hijackers responsible for the September 11th attacks by mapping publicly available details made available following the attacks. Even with the advantages of hindsight and publicly available information on people, places and transactions, it is clear that there is missing data.

Krebs demonstrated the use of an association matrix and link chart of the terrorist network associated with the 19 hijackers responsible for the September 11th attacks by mapping publicly available details made available following the attacks. Even with the advantages of hindsight and publicly available information on people, places and transactions, it is clear that there is missing data.

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

Alternatively, Picarelli argued that use of link analysis techniques could have been used to identify and potentially prevent illicit activities within the Aum Shinrikyo network. “We must be careful of ‘guilt by association’. Being linked to a terrorist does not prove guilt – but it does invite investigation.” Balancing the legal concepts of probable cause, right to privacy and freedom of association become challenging when reviewing potentially sensitive data with the objective to prevent crime or illegal activity that has not yet occurred.

Alternatively, Picarelli argued that use of link analysis techniques could have been used to identify and potentially prevent illicit activities within the Aum Shinrikyo network. “We must be careful of ‘guilt by association’. Being linked to a terrorist does not prove guilt – but it does invite investigation.” Balancing the legal concepts of probable cause, right to privacy and freedom of association become challenging when reviewing potentially sensitive data with the objective to prevent crime or illegal activity that has not yet occurred.

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

Proposed solutions

There are four categories of proposed link analysis solutions:

There are four categories of proposed link analysis solutions:

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

1. Heuristic-based

Heuristic-based

基于启发式的

1. Template-based

Template-based

基于模板的

1. Similarity-based

Similarity-based

基于相似性的

1. Statistical

Statistical

统计方法

Heuristic-based tools utilize decision rules that are distilled from expert knowledge using structured data. Template-based tools employ Natural Language Processing (NLP) to extract details from unstructured data that are matched to pre-defined templates. Similarity-based approaches use weighted scoring to compare attributes and identify potential links. Statistical approaches identify potential links based on lexical statistics.

Heuristic-based tools utilize decision rules that are distilled from expert knowledge using structured data. Template-based tools employ Natural Language Processing (NLP) to extract details from unstructured data that are matched to pre-defined templates. Similarity-based approaches use weighted scoring to compare attributes and identify potential links. Statistical approaches identify potential links based on lexical statistics.

基于启发式的工具运用从专家知识中提取出来的决策规则对结构化数据进行操作。基于模板的工具使用自然语言处理(Natural Language Processing，NLP)从非结构化数据中提取与预定义模板匹配的细节。基于相似度的方法使用加权评分来比较属性和识别潜在的链接。统计方法基于词汇统计识别潜在的链接。

CrimeNet explorer

J.J. Xu and H. Chen propose a framework for automated network analysis and visualization called CrimeNet Explorer. This framework includes the following elements:

J.J. Xu and H. Chen propose a framework for automated network analysis and visualization called CrimeNet Explorer. This framework includes the following elements:

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

• Network Creation through a concept space approach that uses “co-occurrence weight to measure the frequency with which two words or phrases appear in the same document. The more frequently two words or phrases appear together, the more likely it will be that they are related”.

通过概念空间方法创建网络，该方法使用“共现网络”来衡量两个单词或短语在同一文档中出现的频率。两个单词或短语在一起出现的频率越高，它们关联的可能性就越大。

• Network Partition using “hierarchical clustering to partition a network into subgroups based on relational strength”.

网络分区通过“根据关系强度的分层聚类，将网络划分为子组”而实现。

• Structural Analysis through “three centrality measures (degree, betweenness, and closeness) to identify central members in a given subgroup. CrimeNet Explorer employed Dijkstra’s shortest-path algorithm to calculate the betweenness and closeness from a single node to all other nodes in the subgroup.

通过“三种中心性度量（度，间隔度和紧密度）来识别给定子集中的中心成员”进行结构分析。CrimeNet Explorer使用Dijkstra的最短路径算法来计算从单个节点到子组中所有其他节点的间隔度和紧密度。

• Network Visualization using Torgerson’s metric multidimensional scaling (MDS) algorithm.

使用Torgerson的度量多维标度（MDS）算法进行网络可视化。

References

!-参见 http: / / en.wikipedia. org / wiki / wikipedia: 如何使用标记创建引用的脚注，这些标记将自动出现在这里 --

External links

• Bartolini, I; Ciaccia, P.. Imagination: Accurate Image Annotation Using Link-Analysis Techniques. 

• Link Analysis and Crime - An Examination

• Elink Schuurman MW, Srisaenpang S, Pinitsoontorn S, Bijleveld I, Vaeteewoothacharn K, Methapat C., The rapid village survey in tuberculosis control, Tuber Lung Dis. 1996 Dec;77(6):549-54.

• Gunhee, K., Faloutsos, C, Hebert, M, Unsupervised Modeling of Object Categories Using Link Analysis Techniques.

• McGehee, R., Intelligence Report.

• Ressler, S., Social Network Analysis as an Approach to Combat Terrorism: Past, Present and Future Research.

• RFFlow, How to Draw a Link Analysis Diagram.

• IBM i2 Analyst's Notebook Premium

• Silberschatz, A. (1996). "What Makes Patterns Interesting in Knowledge Discovery Systems". IEEE Transactions on Knowledge and Data Engineering. 8 (6): 970–974. CiteSeerX 10.1.1.53.2780. doi:10.1109/69.553165.

• Terrorist & Rebel Link Analysis Feed (TR-LAF)

• Workshop on Link Analysis: Dynamics and Static of Large Networks (LinkKDD2006) August 20, 2006

• ClueMaker

• Data Walk

Category:Network theory

范畴: 网络理论

This page was moved from wikipedia:en:Link analysis. Its edit history can be viewed at 链路分析/edithistory