Notice of Violation of IEEE Publication Principles
“Detecting Critical Regions in Covert Networks: A Ca Study of 9/11 Terrorists Networks”
by Nasrullah Memon, Kim C. Kristoffern, David L. Hicks, and Henrik Legind Larn
in the Proceedings of the 11th International Conference on Information Visualization (IV), July 2007
After careful and considered review of the content and authorship of this paper by a duly constituted expert committee, this paper has been found to be in violation of IEEE’s Publication Principles.
This paper has copied portions of text from the sources cited below. The lead author, Nasrullah Memon, was found to be solely responsible for the violation. The original text was copied without attribution (including appropriate references to the original author(s) and/or paper title) and without permission.
“Clique Relaxations in Social Network Analysis: The Maximum k-plex Problem”
by B. Balasundaram, S. Butenko, I. V. Hicks, S. Sachdeva
Posted online, January 2006
“Network Analysis of Knowledge Construction in Asynchronous Learning Networks” by Aviv, Reuven; Erlich, Zippy; Ravid, Gilad; Geva, Aviva
in the Journal of Asynchronous Learning Networks, Vol 7, No 3, 2003
Detecting Critical Regions in Covert Networks: A Ca Study of 9/11 Terrorists
Network
Nasrullah Memon Department of Computer Science
and Engineering
Aalborg Universitet
Niels Bohrs Vej 8, DK-6700 Esbjerg
i5和i7的区别Denmark
nasrullah@cs.aaue.dk
Kim C. Kristoffern
Department of Computer Science
and Engineering
Aalborg Universitet
Niels Bohrs Vej 8, DK-6700 Esbjerg
Denmark
kck@aaue.dk
Henrik Legind Larn
Department of Computer Science
and Engineering
Aalborg Universitet
Niels Bohrs Vej 8, DK-6700 Esbjerg
Denmark
legind@cs.aaue.dk
David L. Hicks
Department of Computer Science
and Engineering
Aalborg Universitet
Niels Bohrs Vej 8, DK-6700 Esbjerg
Denmark
hicks@cs.aaue.dk
Abstract
This paper prents the study of structural cohesion which is discusd in Social Network Analysis (
SNA), but can also be ud in veral other important application areas including investigative data mining for destabilizing terrorist networks. Structural cohesion is defined as the number of actors who, if removed from a group, would disconnect the group. In this paper we discuss structural cohesion concepts, such as cliques, n-cliques, n-clans and k-plex to determine familiarity, robustness and reachability within subgroups of the 9/11 terrorist network. Moreover we also propo a methodology of detecting critical regions in covet networks; removing/ capturing tho nodes will disrupt most of the network.
Keywords
Structural Analysis, Destabilizing Terrorist Networks, Critical Regions in Covert Networks, Investigative Data Mining
1.Introduction
In the wake of the information revolution, the interest in studying the network structure of organizations, in particular criminal in nature, has incread manifold. Social network concepts, despite their versatility, have come to the forefront especially for the applications. A social network is usually reprented by a graph, in which the t of vertices corresponds to the “actors” in a social
network and the edges correspond to the “ties” between them [1]. Actors can be people, and examples of a tie between two actors include the acquaintance, friendship, or other type of association between them, such as attending the same flight training school at the same time. Alternately, actors can be terrorist cells, with ties reprenting communication between them for making planning for new attack. Thus, graphs can be ud to conveniently model any such information and to make important deductions.
This paper introduces and studies the structural cohesion, which aris in analysis of cohesive subgroups in social networks. Structural cohesion is often ud to explain and develop sociological theories. Members of a cohesive subgroup tend to share information, have homogeneity of thought, identity, beliefs, behavior, even food habits and illness [2]. Structural cohesion is also believed to influence emergence of connsus among group members. Examples of cohesive subgroups include religious cults, terrorist cells, criminal gangs, military platoons, sports teams and conferences, work groups etc. Modeling a cohesive subgroup mathematically has long been a subject of interest in social network analysis.
The aim of the detection of den clusters is to find maximal subts of points (with their relationships) with a high density in the cluster and relatively few relationships to other parts of the n
etwork. Graph theory gives a number of concepts and procedures that aims to detect maximal subgraphs in a graph (or network) that have a certain property and loos this property by adding another point and its relationships to the subgraph. In an undirected network, a clique is a maximal subgraph of at least three points in which all points are directly connected with one another. The concept clique has been
generalized to n-cliques . In an n-clique , between any pair of points in the clique a path of length n or less exists in the graph. Such a path may go through points outside the clique, thus causing a larger distance between the points in the clique itlf (or even disconnected cliques). An n-clan is an n-clique where the distance in the clique is also maximally n . In this paper we u bottom up approaches of cohesion analysis (cliques, n-cliques, n-clans, and k-plex) on a datat shown in Figure1.
Modeling a cohesive subgroup mathematically has long been a subject of interest in social network analysis. One of the earliest graph models ud for studying cohesive subgroups was the clique model [3]. A clique is a subgraph in which there is an edge between any two vertices. However, the clique approach has been criticized for its overly restrictive nature [2, 4] and modeling
disadvantages [5, 6].
Figure 1. The datat of 9/11 hijackers and their affiliates. The datat originally constructed by Valdis Krebs [16], but re-constructed in our investigative data mining
iMiner, using metadata of every terrorist.
Clique models idealize three important structural properties that are expected of a cohesive subgroup, namely, familiarity (each vertex has many neighbors and only a few strangers in the group), reachability (a low diameter, facilitating fast communication between the
group members) and robustness (high connectivity,
making it difficult to destroy the group by removing
members).
Different models relax different aspects of a cohesive
subgroup. Luce R., introduced a distance bad model
called n-clique [17] and Alba R., introduced a diameter
bad model called n-club [4]. The models were also
studied along with a variant called n-clan by Mokken [8].
However, their originally propod definitions required
some modifications to be more meaningful
mathematically. The drawbacks are pointed out and the
models are appropriately redefined by Balasundaram et al.
[7]. All the models emphasize the need for high
reachability inside a cohesive subgroup and have their
own merits and demerits as models of cohesiveness.
Some direct application areas of social networks include
邗沟
studying terrorist networks [9, 10], which is esntially a special application of criminal network analysis that is
intended to study organized crimes such as terrorism, narcotics and money laundering [11,12]. Concepts of social network analysis provide suitable data mining tools for this purpo [13, 14, 15, 21]. 2. Social Network Analysis Description and analysis of social relations is an important aspect of the social sciences. Such relations may be formal, as within or between organizations, or informal, like friendships. In the last three decades an increasing number of social scientists from different disciplines have ud network analysis or graph theory for the analysis and description of social relations. Application of SNA can be found in the work of anthropologists, social-psychological properties of configurations of points and lines. A well known problem of the graph theory is the terminology. Points are some times called vertices or nodes (also known as actors or entities in SNA terminology), while the lines have names like edges or arcs (also called ties in SNA terminology).
3.Literature Review
Since 9/11 much work has been done on the concept of the “Transnational Terrorist Networks”. However, the concept of centralized nation states facing a decentralized, disperd enemy is not an
entirely new one. Arquilla and Ronfeldt [18] propod the idea that it takes a network to beat a network. They propod that the US military needs to become more decentralized in terms of its command and control structures and create a network with other government departments in order to be more effective in their fight against a decentralized networked enemy.
The Social Network Analysis community has also worked on this area. The leading rearch in this field has been by Kathleen M. Carley [19]. Carley address the effects of disrupting a centralized hierarchy compared to a decentralized disperd network. The rearch showed how the different networks reform after the removal of central nodes.
Contractor and Monge [20] ud the social network approach, which could be applied to a terrorist threat. They introduced the idea of a multi-level, multi-theoretical network. The multi-level aspects of this theory, address the complex systems idea of scale. Memon N. and H. L. Larn [14, 15] recently introduced practical approaches and algorithms for analyzing and destabilizing terrorist networks. They propod a novel approach for constructing the hierarchy of non-hierarchical covert and disperd networks. Using the approach, intelligence agencies may easily find the hierarchical structure of the dark networks. The intelligence agencies also can discover the important nodes in the network and can determine how much the efficiency of the network is affected by eradicating so
me important nodes. The approaches/ techniques/ algorithms mentioned [14, 15] are implemented in a software prototype known as investigative data mining software “iMiner”.
Investigative Data Mining (IDM) is defined as “the technique which models data to predict the structure of a non-hierarchical network, determine associations and help in destabilizing the terrorist networks”.
Investigative Data Mining differs from traditional data mining applications in significant ways. Traditional data mining is generally applied against large transaction databas in order to classify people according to transaction characteristics and extra pattern in widespread applicability. The problem in IDM is to focus on a smaller number of subjects within a large background population and identify links and relationships from a far wider variety of activities.
It is important for national curity to understand the structure of terrorist cells that make such cells efficient and flexible. It is esntial to be aware of what does a particular cell / network look like, how does it evolve, and how can the evolution of its structure be mapped?
一分米
4.Ca Study
Figure 1 shows an example of a terrorist network, which maps the links between terrorists involved in the tragic events of September 11, 2001. This graph was constructed
数学世界in [16] using the public data that were available before,
but collected after the event. Even though the information mapped in this network is by no means complete, its analysis may still provide valuable insights into the structure of a terrorist organization. This graph is reconstructed using metadata of every node in our software prototype iMiner.
In this ca study we discuss the u of the four concepts: cliques, n-cliques, n-clans, and k-plex. The datat, which describes the network from Figure 1, has been applied to each of the four concepts. The statistics from the results
are listed in table 1.
Table 1. Statistics from the results
Groups’
Total
Number
Groups’
Maximum Size
Groups’
Minimum
Size
Clique 41 6 3 N-clique 38 23 5 N-Clan 22 23 5 K-Plex 493 7 3 Each node reprents a specific person from the datat,
人这一辈子so the number of nodes should be the same for all concepts. Each concept generated a different number of groups: for example, n-clan concept generates 22 groups while the k-plex concept generates 493 groups. The n-clique generates 38 groups and the clique concept generates 41 groups. For each of the concepts the maximum size and minimum size of a group has also been collected and shown in Table 1.
The statistics indicate that even with a relatively small datat a huge number of groups could be generated. The groups generated are analyzed, in order to identify the best candidate nodes for destabilizing the specific network.
a声调Figure 2 shows how many groups each member participates in, using respectively clique, n-clique, n-clan and k-plex. As we can e some of the members participate in many groups while other members participate in few groups. We say that a member that participates in many groups, compared to the total number
of groups, has a high participation index, while a member participates in few groups, compared to the total number
of groups has a low participation index. Participation index is defined as participation of a particular member in
different groups generated by the various concepts of structural cohesion / cohesion analysis.
For example we take a look at a member Mohamed Atta (node 33) in the matrix generated using the k-plex concept, has participated in 230 groups and the total number of groups is 493. This gives a participation index equal to 230/493, approximately 0.5.
自学考试网官网
If the participation index is clor to 1, it means that member has participated in most of the groups, and if the participation index is clor to 0, it means that the member’s participation is negligible.
From the variation en in the participation index we conclude that the choice of concept has an important influence on the participation index. It ems like using the concepts n-clique and n-clan results in higher participation indices, while the concepts clique and k-plex results in lower participation indices.
The three members described in Table 2, can roughly be en as a picture of arch types or roles in the network. In most cas a member is not 100 percent an arch type, but a combination of the three types. What type a member will match best in a specific situation will also be dependent on other factors, e.g. the pha of the operation conducted by the network.
Table 2. Participation index
Member 33 Member 37 Member 55
Clique 0.293 0 0.098 N-Clique 0.947 0.026 0.553 N-Clan 0.909 0.045 0.455 K-Plex 0.467 0.008 0.152
reprentative or coordinator), leaders and followers. Brokers encompass members working with logistics, communications, etc. Leaders encompass leaders at all levels, using the military terms this means officers. Followers encompass the members that can be compared to the infantry in military terms.
The task of the broker is to provide supplies of weapons, money, identity cards, etc., to the network. Often a broker is also preparing hous and cars for the network. The broker sometimes is the member being the cure communication link between the different groups in the network. As such the broker is often related to a large number of groups in the network, being a key member in tting up the platform for the operation. Member 33 (Mohamed Atta) could as such be an example of a broker. The task of the leader is, of cour, to lead one or more groups in the network. As described, leaders in the network can be found at veral levels, from the member leading a group to the leader running the network. Leaders tend to “hide in the crowd”, and in some cas they are related to a large number of groups, in other cas they are related to only a small number of groups. As such they can be harder to find. Though in most cas the leader is related to many groups, they usually will still have a lower participation index than the broker, and the leader related to few groups will have a participation index higher than the followers. Nawaf Alhazmi (node # 55) could as such be an example of a leader.
The task of the follower is to be the executing part and following orders from leaders. Followers usually have very limited knowledge about the overall plan. The follower is a member of just a few groups since he has no direct importance for other groups in the network, like for instance the broker. Mamduh Salem (node # 37) could as such be an example of a follower.
个人事迹材料Figure 2. The participation of the members of the 9-11 terrorists network in various groups using the
concepts Clique, n-clique, n-clan and k-plex.
5.Detecting Critical Regions Often the generated datat is simply too huge. In that
ca the analyst may focus on the part of the datat that
