∎

11institutetext: F. Gilbert 22institutetext: P. Simonetto 33institutetext: F.
Zaidi 44institutetext: R. Bourqui 55institutetext: CNRS UMR5800 LaBRI and
INRIA Bordeaux - Sud Ouest, France,
Tel.: +33 540 00 84 27
Fax: +33 540 00 66 69
55email: {frederic.gilbert, paolo.simonetto, faraz.zaidi,
<EMAIL_ADDRESS>66institutetext: F. Jourdan 77institutetext: INRA,
UMR1089, Toulouse, France
<EMAIL_ADDRESS>
Tel.: +33 561 28 57 15

# Communities and Hierarchical Structures in Dynamic Social Networks: Analysis
and Visualization

Frédéric Gilbert  Paolo Simonetto  Faraz Zaidi  Fabien Jourdan  Romain Bourqui

(Received: date / Accepted: date)

###### Abstract

Detection of community structures in social networks has attracted lots of
attention in the domain of sociology and behavioral sciences. Social networks
also exhibit dynamic nature as these networks change continuously with the
passage of time. Social networks might also present a hierarchical structure
led by individuals that play important roles in a society such as Managers and
Decision Makers. Detection and Visualization of these networks changing over
time is a challenging problem where communities change as a function of events
taking place in the society and the role people play in it.

In this paper we address these issues by presenting a system to analyze
dynamic social networks. The proposed system is based on dynamic graph
discretization and graph clustering. The system allows detection of major
structural changes taking place in social communities over time and reveals
hierarchies by identifying influential people in a social networks. We use two
different data sets for the empirical evaluation and observe that our system
helps to discover interesting facts about the social and hierarchical
structures present in these social networks.

###### Keywords:

Dynamic Social Networks Dynamic Network Visualization Clustering Dynamic
Graphs Influence Hierarchy in Social Networks

††journal: Social Network Analysis and Mining

##  1 Introduction

A social network is a set of people connected by a set of social relationships
wasserman:95 ; scott00  such as friendship rapoport61  and business
collaboration watts98 ; newman01 . Mathematically these networks can be
represented by a graph where nodes represent people and edges represent their
relationships. Past work in social network analysis wasserman:95  has shown
that the knowledge of community structure and relationship strength has
important applications in web analytics chakrabarti:98 , marketing studies
domingos:01 , homeland security yang07 ; subr08  and disease modeling
kretzschmar96 ; eubank04 .

Visual analysis of social networks is an integral component of the field of
social network analysis freeman04 . Visualizing community structures present
in social networks and identifying people who play important roles within a
network can reveal interesting information specially by exploiting the
temporal evolution of relationships. Social networks can exhibit temporal
dynamics in a number of ways. The instances in the data may appear and
disappear over time whereby different time windows may exhibit different
characteristics. For example, a person might change his affiliation with a
business organization by joining a different business enterprise and
developing new social ties within this new environment. Moreover, the
relationships may represent events and associations that are significant at a
particular point of time, such as new job opportunities, or the establishment
of a new business organization. If this is the case, then the temporal
dimension associated with these events play a key role to capture important
information.

A more recent application of social network analysis has been in the study of
counter terrorism memon07 ; maeno09 ; adler07 ; yang07 . Studying social
networks of potential terrorists can help us to uncover the organizational
structure of terrorist networks, predict terrorist activities by identifying
events and possibly disclose the identity of master minds behind the criminal
activities.

This was the initial problem that motivated this research where we were
required to analyze the data of cell phone calls (see section 3 for more
details). The goal was to analyze the dynamics taking place in social network
over time and infer an influence hierarchy. The social network was represented
by cell phone data where two people were connected if they communicated with
each other through a cell phone . The initial work of this research was
focused on this particular problem whereas we present an extended system in
this paper which is generic and robust to handle a variety of data sets.

Other examples of dynamic social networks include email network diesner05 ,
where the time of an email sent, the co-authorship network of scientific
publications newman01  with the year of publication and the actor-actor
collaboration network of movies barabasi99  with its year of release. All
these examples of social networks have temporal dimensions associated with
them and must be exploited to analyze and understand these networks.

In this paper, we present a system, called DySNAV abbreviate for Dynamic
Social Network Analysis and Visualization which helps a user to analyze the
dynamics of community structures present in these social networks. People form
community structures by frequently communicating or collaborating with certain
people as compared to others. These communities undergo changes with the
passage of time as the individuals, their relationships and their roles change
in the social network. We try to identify these dynamics by focusing on
communities and their changing relationships through visualization and
discover important events by observing any radical changes in the structure of
social network. We also infer a role hierarchy by identifying the most
influential people in the social network.

The paper is organized as follows: In the following section, we present the
related work. In section 3, we present different data sets used for
experimentation. Section 4 presents the proposed system comprising of four
major steps. The first step is data discretization described in section 4.1.
This is followed by the decomposition step in section 4.2 where the community
structures are identified. The details of how changes are detected in the
community structures through visualization are presented in section 4.3. In
section 4.4, we introduce a novel heuristic to determine the influence
hierarchy in the network. As a case study, we use our system to analyze two
dynamic social networks in section 5. Finally in section 6, we present
conclusions and directions for future research.

##  2 Related work

Community detection in social networks has attracted lots of attention in the
domain of sociology. A more generic formalism for the term community is the
term cluster. Sociologists use the term community coleman64  as compared to
the statistical and data mining domain where people use the term cluster
tryon39  to refer to the same concept. A cluster might not necessarily
represent a community but throughout this paper, we use the terms
interchangeably to refer to the same concept. Several surveys jain99 ;
berkhin02 ; schaeffer07  are available addressing the clustering or community
detection problem. Some approaches ACJM03 ; newman04 ; girvan02  have
performed better than the others for the discovery of communities in social
networks. Researchers have also shown interest in discovering changing
clusters in dynamic data Kalnis:05  and clustering evolving data streams
aggarwal:03 . However, these techniques are either insufficient or inefficient
to characterize the changes in community structures. Since the interactions
taking place between individuals can be characterized by a single relationship
(for example: a weighted edge), interactions between communities inherit a
number of ways that can establish an interaction between two communities over
a passage of time. Since most of the existing techniques are adapted to handle
changes occurring in individuals rather than communities, the goal of our
approach is clearly different from others.

Social network visualization has also attracted much interest as images of
social networks have provided investigators with new insights about these
networksfreeman00 . Different visualization softwares and tools exist for
social network analysis such as heer05 ; baur02 ; bilgic06 ; shen06  but these
networks do not handle the temporal dimension of a network. The readers are
recommended freeman00  for a more detailed review of the literature on social
network visualization.

Research in the domain of analysis and visualization of dynamic graphs has
attracted limited interest. For example, Kang _et al._ kang07  introduce a
tool called C-Group for temporal analysis of social networks. The tool focuses
on a pair of individuals rather than analyzing overall structural changes in
the entire network. Gloor _et al._ gloor04  proposes a sliding time frame
algorithm to display active ties between actors in a sliding time frame
covering a time interval. The approach works well to trace the evolution of
relationships between individuals but does not capture the evolution of the
community structures in the entire social network. Sarkar and Moore sarkar05
present a method for modeling relationships that change over time. The idea is
to develop an understanding of historical data and to predict future
interactions. The model can be used to study the behavior of individual
relationships but requires adaptation to model the behavior of a group of
people. SoNIA (Social Network Image Animator) demoll06  is a package for
animating network dynamics over time and is not intended to be a network
analysis tool. Rather than focusing on calculating network properties and
indices, it is designed to facilitate the exploration of dynamic relational
data, and the comparison of various layout techniques for making reliable
animations of networks. It does not capture the dynamics of a group of
people(cluster) and focuses on aggregating and transforming dynamic data to
create a stable social space which is necessary to create a meaningful
visualization. Moody _et al._ moody05  introduce two types of visualizations:
flip books where nodes remain in a constant position and arcs fill in the
holes among these nodes and dynamic movies where nodes move as a function of
relational changes taking place in the network.

These systems perform well to exploit the temporal dimensions of a dynamic
network focusing on changes and transitivity of individuals or their
relationships. The system we present in this paper helps to discover
structural changes in the entire network by studying the evolution of
communities and the goals are clearly different from the other systems
presented in this section.

Figure 1: Framework of the Proposed System representing the four major steps.

##  3 Data Sets

We use two different data sets for the empirical evaluation of our system.

Catalano/Vidro data set is a fictitious data presented in the IEEE VAST 2008
CHALLENGE 111http://www.cs.umd.edu/hcil/VASTchallenge08/ for visualization and
extraction of information about a terrorist group in the entire social
network. It consists the information of $9834$ phone calls between $400$ cell
phones over a $10$ day period in June 2006 in the Isla Del Sueno. The data set
records each call as 5-tuple (from$\\_$user$\\_$id, to$\\_$user$\\_$id,
timestamp, call$\\_$duration, cell$\\_$tower$\\_$location). This is an
interesting example as precise information about call records can be made
available through any cell phone network. Tracking cell phone records with the
associated temporal dimension can help us find or predict an event by an
unexpected rise in the call frequency, distribution of important information,
identity of people responsible for communicating information in the network
etc.

The other example is the Co-Authorship Network which is a network of
researchers where two people are connected to each other if they have co-
authored a scientific artifact. The year of publication is the temporal
information associated to each artifact. The bibliographic data was downloaded
from the DBLP Computer Science Bibliography website
222http://www.informatik.uni-trier.de/~ley/db/ and contains data till the year
2008. From the complete data set, a subset was generated by selecting a
researcher named Ulrik Brandes and taking all the researchers connected to him
at distance two i.e. the people who have directly co-authored with him, or
have co-authored with a person having directly co-authored with Ulrik Brandes.
The data set is represented by 5-tuple
(Author1,Author2,Year,Strength,Title_of_Artifact). The strength parameter was
set to a default value of 1 for all entries. A complicated metric can be used
such as if an artifact is co-authored by exactly two people, it will have a
high strength whereas a high number of co-authors can represent a weak
relationship between any two of its authors. The data set contains all the
publications of Ulrik Brandes available on the DBLP website from the year 1997
till the year 2008 containing approximately 900 researchers and 6500 edges
between them.

##  4 Proposed System

Figure 2: Screen Shot of the Proposed System. Different windows showing the
various visualizations available in the system. Top Left: Graph for a selected
interval with edges present in that time interval only. Bottom Left:
Similarity Graph of different time intervals with time on the x-axis and
different values of filter on the y-axis. Top Middle:List of all the clusters
found in the Graph displayed in Graph View. Top Right: Contents of a Cluster.
Bottom Right: Influence Hierarchy representing the most influential people
closer to the root of the tree.

A dynamic social network can be defined as a dynamic graph $G=(V,E)$ where $V$
represents the set of nodes (people) and $E$ represents the set of edges
(relationships). Every edge $e=(u,v)\in E$ has an attribute depicting the Time
described over a time period $[0\dots T]$. The graph $G_{[t1,t2]}$ represents
the nodes of the graph with only the edges present during the time interval
$[t1,t2]:0\leq t1<t2\leq T$.

The main idea of the system is based on the framework introduced in bourqui09
proposed by the authors and was a preliminary version of this on going
research. Figure 1 illustrates the four steps of the framework upon which this
system is built. In this paper, we present a fully operational and interactive
system based on the principles introduced in bourqui09  which is composed of
several steps described below.

The first step is to convert the dynamic graph into a set of static graphs
where each static graph corresponds to a time interval. The discretization
factor is taken as input which can be adjusted by the user interactively.

The second step clusters each static graph separately using an overlapping
clustering algorithm, to produce Fuzzy Clusters. This step allows us to
identify communities in the network but also its _pivots_ (vertices shared by
several clusters) while being insensitive to minor changes in the network as
proven by bourqui09a .

The third step detects major structural changes in the network. We compare the
clusterings obtained on every pair of successive static graphs using a
similarity measure described in section 4.3. A low similarity indicates major
changes during the period corresponding to the pair of snapshots while a high
similarity value correspond to stable periods where the topological structure
of the network does not go any major changes. Thus, once we have the
similarity matrix from clusterings computed in step $2$, we can decompose the
temporal changes in the input network into periods of high activity and
_consensus_ communities during stable periods.

The last step consists of finding a _role_ or _influence hierarchy_ in the
_consensus_ communities filtered from step $3$. We define the _influence
hierarchy_ as a tree where the height of a node represents the influence of
that node in the network. Our technique is based on the Delta efficiency
metric ML06 ; larsen07  which computes the importance of a vertex with respect
to the flow of information in the entire network. Using this Delta efficiency
metric and Kruskal’s algorithm K56  for minimum spanning tree generation we
are able to infer the influence hierarchy in the network.

The input to the system is a comma separated text file. Each line in the file
is a 5-tuple (user_id_1, user_id_2, timestamp, relationship$\\_$strength,
relationship$\\_$class). The user_id_1 and user_id_2 are identification
numbers or strings used to identify two people in the social network. The
timestamp is in the format yyyy/mm/dd-hr:mn:sc. The user is not required to
enter all the information. For example if there is only year and months data
available for a data set, the user can only enter the data in the format
yyyy/mm in each tuple. In case if the data is available for a 24 hour interval
with a precision of minutes, in that case, the user is required to enter all
the information by entering the same year, month, and day data for all the
entries like 2009/12/01-11:24 and change only the hour and minute information
for other entries. The parameter relationship$\\_$strength represents an
integer value to assign a numerical weight that can be used as metric to
distinguish between strong and weak relationships. As an example, for an email
network, the size of the message can be used as an attribute of the
relationship. Any default value can be assigned to all relationships if no
real value exists. The parameter relationship$\\_$class represents a nominal
value to help classify relationships. Again considering the example of the
email network, an IP address can be used as a class and any default value can
be used for all the records. To load a data set in the system, the user is
required to choose a file in the mentioned file format by clicking on the
choose file option in the attribute panel of the system as can be seen in
Figure 2.

The system comprises of five windows to display information and a panel
(attribute panel) to set the values of different attributes as shown in Figure
2. The details explaining the implications of different attributes are
described in the following sections. The Graph View window is used to display
the social network as a node-link diagram where the graph is laid out using a
force directed algorithm proposed by Hachul and Junger hachul04 . Force
directed algorithms are well suited for the visualization of community
structures as the nodes densely connected to each other are pushed in close
proximity and disconnected nodes are pushed far away. The Similarity Graph
window is used to display a graph of graphs, i.e. each node in this graph
represents a graph where the x-axis represents the time line and the y-axis
represents different values used to filter edges specified in the parameter
Number of Slices. This visualization is used to analyze the dynamics of the
graph as it changes over time (details are explained in the following
sections). The Cluster List window contains a list of the clusters found in
the graph. Clicking on one of the clusters in this list displays the contents
of the cluster in the Cluster View window. Clicking on a node in this graph
displays the graph associated to this node in the Graph View window. There is
a small widget in the Similarity Graph window in the bottom left corner
representing the minimum and maximum values of the strength metric and the
color gradients associated to these values.

Finally the Hierarchy View window is used to display the influence hierarchy
extracted from the social network representing how influential a person is in
the entire network. The layout algorithm used to display the hierarchy is
called the Walker tree with improved implementation and was proposed by
Buchheim et al. buchheim02 . In addition to this hierarchical layout, the tree
can be drawn using another layout known as the Radial Tree first introduced by
kelly03 . The choice of the layout can be selected from the Attribute Panel
where each layout has its own benefits. The Improved Walker layout helps to
reveal the influence hierarchy as it is drawn top-down and the radial tree
layout places the root at the center and the nodes connected to the root
around it. Although this layout does not help to reveal the hierarchy but it
does help to identify the central nodes as the leaves are placed far away from
the center and the important nodes closer to the center in the layout.

The system is interactive where the size of each window can be changed. Zoom-
in and zoom-out are associated with the scroll wheel of the mouse. The values
in the attribute panel can be modified interactively where the corresponding
graphs and their layouts change as the associated compute or apply buttons are
clicked. If the value of the Clustering($\tau$) is changed, the new clustering
is calculated as soon as the scroll bar is released.

The proposed framework consists of four major steps which are discussed in
details below.

###  4.1 Graph Discretization

Once the data is loaded in the system, the first processing step of the
proposed system is to convert the dynamic graph $G$ into a set of graphs
representing snapshots of the graph at different time intervals. From $G$, we
obtain a sequence of snapshots
$G_{[0,\epsilon]},\ldots,G_{[T-\epsilon,T]}=G_{1},\ldots,G_{\alpha}$, where
$\alpha$ is the number of graphs obtained and $\epsilon$ is the discretization
factor. The graph $G_{[t,t+\epsilon]}$ is the static snapshot corresponding to
the time interval $[t,t+\epsilon]$ (i.e. the graph containing all vertices and
edges involved during the time period $[t,t+\epsilon]$). The total number of
graphs generated this way are equal to the total time period $[0,T]$ divided
by the discretization factor $\epsilon$ which we represent by the factor
$\alpha$. The system allows the user to set the value of $\epsilon$ which
depends on the granularity of the time stamps present in the data set.

Recall that the input data allows a relationship_strength to be specified for
each relationship. We calculate metrics using this value that can be
associated to each edge. Currently the system provides three different
calculations: the Total time, Average time and Occurrency. Total time refers
to the commulative sum of relationship_strength for all occurrences of nodes
$(u,v)$. The average time is the average calculated for all the instances and
the Occurrency is the frequency of occurrences of a relationship between any
two nodes $(u,v)$. Use of these metrics depend on the data sets and the user’s
interpretation of values associated to a relationship. The user is required to
select the type of metric from the Metric drop down menu.

The system provides a method to filter edges having weak relationships. Since
we cannot set a predefined threshold, we set multiple values to filter out
edges. The user is required to input the Number of slices ($\omega$) which is
a positive integer. The system takes the minimum and the maximum values of the
calculated metric and divides this range into slices as specified by the
parameter $\omega$. For each graph in
$G_{[0,\epsilon]},\ldots,G_{[T-\epsilon,T]}=G_{1},\ldots,G_{\alpha}$, we
obtain $\omega$ graphs. Finally we get $\omega\times\alpha$ graphs which are
drawn in the bottom left window of the system as shown in Figure 2. Each graph
is represented as a node where the placement of the nodes on the x-axis
represents the different time intervals ($\alpha$) and the y-axis represents
the number of slices ($\omega$). We call this graph the Similarity Graph as
each node represents a graph and the nodes are placed in a grid layout.
Clicking on a node displays the contents of the graph in the top left window
as shown in Figure 2. We explain how this layout helps in evaluating the
similarity in the following sections.

###  4.2 Graph decomposition

The input to the graph decomposition step is the set of graphs obtained as a
result of the previous step. The basic idea is by considering two snapshot
graphs corresponding to successive time intervals, they should have “similar”
topologies if the dynamic graph does not undergo drastic changes between the
two time intervals. To capture these topologies, our approach uses a
decomposition algorithm by clustering the graph into smaller components. We
describe the details of the decomposition process below.

####  4.2.1 Strength metric

Our decomposition algorithm is based on the _Strength_ metric, introduced by
Auber _et al._ ACJM03 . This metric quantifies the neighborhood’s cohesion of
a given edge and thus identifies if an edge is an intra-community or an inter-
community edge. The _strength_ of an edge $e$ given by $w_{s}(e)$ is defined
as follows:

$w_{s}(e)=\frac{\gamma_{3,4}(e)}{\gamma_{max}(e)}$

where $\gamma_{3,4}(e)$ is the number of cycles of size $3$ or $4$ the edge
$e$ belongs to, and $\gamma_{max}(e)$ is the maximum possible number of such
cycles. Finally, one can define the _strength_ of a vertex as follows:

$w_{s}(u)={\frac{\sum_{e\in adj(u)}w_{s}(e)}{deg(u)}}$

where $adj(u)$ is the set of edges adjacent to $u$ and $deg(u)$ is the degree
of vertex $u$. The time complexity to calculate the strength metric over all
vertices (V) and edges (E) is $O(|E|\cdot(deg_{max})^{2})$ where $deg_{max}$
is the maximum degree of the graph.

####  4.2.2 Maximal independent set extraction

To identify the _center_ of communities within the network, we use a method
inspired by _MISF_ 333Maximal Independent Set Filtering GK00  where we extract
a maximal set $\nu$ of vertices such that $\forall u,v\in$ $\nu$,
$dist_{G}(u,v)\geq 2$. The advantages of this algorithm are twofold: first, it
gives the number of clusters with respect to the topology of the network and
secondly, this technique guarantees the uniqueness of each found cluster (i.e.
two clusters found by our approach cannot be identical) since a _center_ can
only belong to one cluster.

Notice that since the vertices in $\nu$ are the _center_ of communities, these
vertices should not be the pivots of the network as this may lead to over
fitting a large community instead of several smaller communities. The network
pivot nodes can be identified by low strength values as they are shared by
several communities. Therefore, vertices with high strength values have to be
added to the set $\nu$. To extract such set, we use the algorithm 1.

Input: A graph $G=(V,E)$

Output: A maximal set $\nu$ of vertices at distance at least $2$

vector$\langle$node$\rangle$ $sorted\\_nodes$;

sortNodeWithStrength($G$, $sorted\\_nodes$);

for _unsigned int $i$ from $0$ to (number of vertices in $G$)_ do node $u$ =
$sorted\\_nodes[i]$;

if _$u$ in $G$_ then append($\nu$,$u$);

foreach _node $v$ in neighborhood of $u$_ do remove($G$, $v$);

end remove($G$, $u$);

end end

Algorithm 1 Computation of the set $\nu$. The sortNodeWithStrength ($G$,
$sorted\\_nodes$) method sorts the vertices by decreasing Strength values and
store the result in $sorted\\_nodes$.

The time complexity of the sorting algorithm sortNodeWithStrength(Graph,
vector$\langle$node$\rangle$) used within the algorithm 1 is $O(|V|\cdot
log(|V|))$. It is easy to show that the complexity of the for loop is
$O(|V|+|E|)$. To compute $\nu$, we sort (in descending order) the vertices $V$
according to their strength values as $V^{\prime}$. Thereafter, we iterate
over $V^{\prime}$ adding the top node to $\nu$ and removing it and its
neighbors from $V^{\prime}$ until $|V^{\prime}|$ = $0$. The complexity of this
algorithm is $O(|V|\cdot log(|V|)+|E|)$ in time and $O(|V|+|E|)$ in space.

####  4.2.3 Extracting communities

We use the high strength node set $\nu$ to extract communities from the input
network. The main idea is to build _balls_ with radius $1$ around the vertices
in $\nu$. For each node $u$ $\in$ $\nu$, if an edge $(u,v)$ has a strength
value higher than a given threshold $\tau$, then this edge is considered as an
intra-cluster edge and the node $v$ is added to the community of $u$. The
threshold $\tau$ is a function of the number of vertices and edges in the
network. We consider several values for the threshold,
$\tau_{1},\dots,\tau_{m}$ obtaining $m$ different clusterings at each time
interval. The time complexity of the communities extraction is $O(|E|)$ and
its space complexity $O(|V|+|E|)$. The overall complexity of our decomposition
algorithm is $O(|E|\cdot deg_{max}^{2}+|V|\cdot log(|V|))$ in time and
$O(|V|+|E|)$ in space.

After the Graph decomposition step, we obtain clusterings for each graph in
the Similarity graph. The user can set the value of $\tau$ from the interface
using the slider where the range $[0,1]$ represents the metric strength
calculated on edges as described previously.

###  4.3 Detection of Changes

We denote the clustering set by $C$ where each clustering $C_{i,j}$
corresponds to the decomposition of the graph $G_{i}$ with parameter
$\tau_{j}$. As the decomposed graphs are naturally ordered with respect to
time, the most probable cluster evolution can be found by comparing each
$C_{i,j}$ with each $C_{i+1,k}$ $\forall i,j,k$ such that $1\leq i<n$, $1\leq
j,k\leq m$. We describe a _similarity metric_ in the next section to evaluate
the similarity between each pair of clusterings in $C$.

####  4.3.1 Similarity metric

The _similarity metric_ aims to evaluate the similarity between two
collections drawn over the same elements. It is related to the metric used in
clustering protein-protein interaction networks Algorithm_evaluation . The
metric is based on the concept of _representativeness_. We say that a cluster
$c_{a}\in C_{i,j}$ is a good representative of a cluster $c_{b}\in C_{i+1,k}$
$iff$ $c_{a}$ contains a high ratio of the elements of $c_{b}$ and a small
ratio of elements not in $c_{b}$. We define _directed cluster
representativeness_ as:

$\rho_{c_{a}\rightarrow c_{b}}=c_{a}\cap c_{b}\ /\
|c_{b}|\qquad\rho_{c_{b}\rightarrow c_{a}}=c_{a}\cap c_{b}\ /\ |c_{a}|$

which corresponds to the normalized ratio of the common elements between the
two clusters.

We further define the _undirected cluster representativeness_ , or more simply
_cluster representativeness_ as:

$\rho_{c_{a},c_{b}}=\sqrt{\rho_{c_{a}\rightarrow
c_{b}}\cdot\rho_{c_{b}\rightarrow c_{a}}}$

which corresponds to the geometrical mean of the direct representativeness of
each cluster with respect to the other.

Next, we extend the definition of cluster representativeness to groups of
clusters or clusterings. We say that $C_{i,j}$ is a good representative of
$C_{i+1,k}$ if the former contains a good representative cluster for each
cluster in the latter. As small size clusters tend to bias the
representativeness values, we give more importance to clusters representative
of larger size clusters over smaller ones. We define the _directed clustering
representativeness_ as the weighted average (over the cardinality of the
clustering) of the value of the best cluster representative found in $C_{i,j}$
for each cluster in $C_{i+1,k}$:

$\sigma_{C_{i,j}\rightarrow C_{i+1,k}}=\frac{\sum_{c_{b}\in
C_{i+1,k}}\max_{c_{a}\in
C_{i,j}}\rho_{c_{a},c_{b}}\cdot|c_{b}|}{\sum_{c_{b}\in C_{i+1,k}}|c_{b}|}$

Similarly, we define the _undirected clustering representativeness_ as the
_similarity metric_ :

$\sigma_{C_{i,j},C_{i+1,k}}=\sqrt{\sigma_{C_{i,j}\rightarrow
C_{i+1,k}}\cdot\sigma_{C_{i+1,k}\rightarrow C_{i,j}}}$

####  4.3.2 Clustering Visualization

Under the hypothesis that cluster evolution presents an inertia towards
drastic changes (that means that clusters do not change drastically at each
time step), the similarity between different clusterings helps to identify a
better parameter value $\tau$. Currently, we are unable to select the optimal
value $\tau_{j}$ that gives us the best clustering result for the graph
$G_{i}$. Nevertheless, as a heuristic to estimate a good $\tau$, we detect a
sequence of clusterings $C_{i,j},C_{i+1,k},C_{i+2,l}\dots$ that has a higher
similarity metric at each step than the average.

To study the behavior at two successive time intervals, we calculate the
maximum and the average similarity of two successive clusterings from
$\sigma_{C_{i,j},C_{i+1,k}}$ $1\leq j,k\leq m$. If the difference between the
maximum similarity and the average similarity values is large, this signifies
radical changes in the network whereas if the difference is small, we can
infer that no significant changes occurred in the network between these two
consecutive time intervals. To facilitate this analysis, we use a a visual
representation of the similarity metric value computation between the evolving
clusterings as shown in Figure 2 shows the similarity metric computation and
network changes for the Co-authorship data set. For each clustering $C_{i,j}$,
we add an edge corresponding to clusterings compared through the similarity
metric with $C_{i,j}$. These edges are then weighted with the similarity
metric $\sigma$ and graphically displayed using a varying color scale and/or
varying edge thickness.

To visualize each cluster, the user can select a node in the Similarity Graph
window, all the clusters present in this graph are listed in the Cluster List
window. We can explore these clusters individually by selecting a cluster in
the list and visualize its contents in the top right window as shown in Figure
2.

####  4.3.3 Community Extraction

With time, communities can expand to include new nodes or merge with other
communities or decrease in size by deleting nodes or splitting into subgroups.
Thus, a community at a given time step might appear as two distinct groups
either due to a previous split or a pending merge. To overcome this problem
and obtain a global idea of the community composition, we compute the
consensus communities in the input network. At each time step, each community
is represented by clusters detected. As these clusters represent a snapshot of
the communities, we can follow the community evolution by matching the
clusters between consecutive time intervals.

Let $\overline{C}_{x},\overline{C}_{x+1},\overline{C}_{x+2}\dots$ be the
clusterings $C_{x,j},C_{x+1,k},C_{x+2,l}\dots$ along a similarity path. We
know the similarity metric $\sigma$ for each pair of consecutive
$\overline{C}_{i},\overline{C}_{i+1}$ clusterings and therefore the clustering
representativeness between each $c_{a}\in\overline{C}_{i}$ and
$c_{b}\in\overline{C}_{i+1}$. Thus, we use these values to match the clusters,
and identify the clusters $c_{b}$ that are representative of clusters $c_{a}$.

Calculation of consensus communities between two graphs of different time
intervals is achieved by first selecting a node in the similarity graph by
clicking it, and then selecting another node by holding the ctrl button and
clicking the second node. The path between these two nodes with maximum
similarity is calculated along with the corresponding consensus graph.

The computation of $\sigma$ between two clusterings $C_{i,j},C_{i+1,k}$ is
bounded by the computation of the intersection between each pair of cluster
$c_{a}\in C_{i,j}$, $c_{b}\in C_{i+1,k}$. This step requires at most
$Q^{2}|V|$ comparisons where $Q$ is the maximum cardinality of $C_{i,j}$ and
$V$ is the number of nodes in the network. As each clustering $C_{i,j}$ is
compared with all the clusterings at the following time steps, we calculate
the similarity metric $(\alpha-1)\omega^{2}$ times. Typically $\alpha$ and
$\omega$ are not very large—thus, the overall complexity is acceptable for an
interactive computation. The calculation of the consensus communities depends
on the filtering algorithm chosen by the user, but it is generally bounded by
the computation of the similarity graph.

###  4.4 Influence hierarchy

We define the _influence hierarchy_ as a tree $G_{T}$ = $(V_{T},E_{T})$ where
$V_{T}\subset V$ is a subset of vertices in the social network. The height of
a node $v$ $\in$ $V_{T}$ represents the strength of influence of that node in
the network. Our technique is based on the Delta efficiency metric ML06 ;
larsen07  which computes the importance of a vertex with respect to the flow
of information in the entire network. To quantify the efficiency with which
the nodes in the network exchange information, we use the idea of LM04  to
calculate this efficiency. We know that all nodes exchange information over a
network represented by a graph $G=(V,E)$, and this information can be picked
by other nodes if required. For the experimental data sets, each cell phone
call or each co-authored artifact represents such an exchange of information.
The communication efficiency of the network $\varepsilon_{ij}$ between the
nodes $i$ and $j$ is inversely proportional to the shortest path in the graph
between $i$ and $j$: $\forall i,j\in V$ $\varepsilon_{ij}=1/d_{ij}$, where
$d_{ij}$ is the shortest path between $i$ and $j$. If there is no path between
$i$ and $j$, then $d_{ij}=+\infty$ and $\varepsilon_{ij}=0$. We can quantify
the efficiency of the whole network be calculating $\varepsilon_{ij}$ for each
and every pair of nodes. The average efficiency of the graph $G$ can be
defined as:

$\displaystyle Eff(G)=\sum_{i\neq j\in V}\varepsilon_{ij}\ /\ |V|\cdot(|V|-1)$

This metric gives us the communication efficiency of the network. To find a
hierarchy in the network, we need to evaluate the efficiency or the
_criticality_ of each node as proposed by LM04 . The idea is that if an
important member of the network is removed, the efficiency of the graph should
decrease. We define the Delta Efficiency(DE) of a node as:

$\displaystyle I(node_{i})=\Delta Eff_{i}=Eff(G)-Eff(G\backslash\\{i\\})$

once we have the Delta Efficiency of each node, we can use this efficiency to
assign weights to edges. There are several ways to assign a weight to an edge
if the nodes are weighted. One way is to take the average of the two nodes
connecting an edge. Currently we use the maximum of the two nodes connecting
an edge given by the equation:

$\displaystyle Weight(e_{ij})=Max\\{\Delta Eff_{i},\Delta Eff_{j}\\}$

The term $e_{ij}$ refers to an edge between nodes (i,j) and $\Delta Eff_{i}$
and $\Delta Eff_{j}$ are their respective delta efficiency values. From this
weighted graph, we use Kruskal’s Minimum Spanning Tree algorithm K56  to
generate a tree. This tree reveals the influence hierarchy in the network by
selecting the node having the highest delta efficiency value. The tree can be
calculated by clicking on the compute button and visualized in the Hierarchy
View window.

From the given problem statement of the Catalano/Vidro data set bourqui09 , we
were required to find people with specific roles in the social network. The
Boss, his right hands and his brother. As compared to generic social networks,
in a terrorism network, the leader tries to hide himself in the network and
does not have a high delta efficiency value. The leader is usually in contact
with only a few people who are responsible of diffusing information in the
entire network which we call right hands. Calculating the hierarchy to find
the leader in this network requires some adaptability which can be activated
using the counter terrorism mode from the attribute panel by clicking the
check box. The details of how the hierarchy is calculated in this mode are
explained in the case study (see section 5).

##  5 Case Study

###  5.1 Co-authorship Network data set

Figure 3: Similarity graph for Co-authorship network with focus on Ulrik
Brandes where blue color represents perfect similarity and yellow represents
very low similarity. (a) suggests very high similarity between time intervals
1979-81 and 1982-84. (b) suggests a long period of high similarity between
1988 and 1999. (c) marks a major structural change as between this period, the
similarity drops to a very low value. (d) resurgence of the similarity between
the periods 2003-05 and 2006-08.

As described previously, the co-authorship network was constructed by taking
Ulrik Brandes as the starting point and all the researchers connected to him
at distance 2. The Similarity Graph shown in Figure 3 marks the important
areas that can be used to deduce interesting information. The enclosed area
labeled (a) refers to the similarity between two consecutive time intervals,
1979-81 and 1982-84 represented by blue colored edges between the graphs of
this period. The second interesting period is labeled (b) where high
similarity between 1988 and 1999 can be noticed. This is the period where we
find the first publication of Ulrik Brandes(1997). He finished his Ph.D.
thesis in the year 1999. As the graph contains people closely connected to
him, they are people working in the same domain (graph drawing and information
visualization) and probably most of them are from the same university where
Ulrik Brandes did his doctorate, justifying the high similarity between graphs
of this period. Research teams work on similar topics and there is always a
tendency that while being at the same university, people tend to work with the
same group of people with whom they have worked earlier. Clustering the graph
for these periods would result in more or less the same clusters and stability
over a time period in the collaboration behavior of researchers.

Between the year 1997-99 and 2000-02, there is a decrease in the similarity
values which continues to decrease between the period 2000-02 and 2003-2005 as
labeled (c) in the figure. During this period, Ulrik Brandes first moved to
the University of Sydney and then to Brown University for post-doctoral
research fellowships. and thus the similarity values show a major structural
change between these periods. From the year 2003, he has been working at the
University of Konstanz and thus the similarity between the period 2003-05 and
2006-08 represent stability in the collaboration pattern of Ulrik Brandes.

From Figure 2, the hierarchy of this network is visible where we find Ulrik
Brandes at the root which is consistent with the way the data set was
collected. Since he plays the role of the central person for information
interchange between the rest, it is no surprise that we find him as the person
with the highest delta efficiency value. The tree has a depth of 2, again an
implication of the way the data set was collected since we consider only
authors lying at distance 2 from Ulrik Brandes. On the other hand, tree is
very wide since he is an author who has collaborated with many people. These
people themselves have collaborated with many people and such an example is
depicted in Figure 2 where Michael Kaufmann (additional reviewer of Ph.D.
thesis of Ulrik Brandes) is highlighted in the Graph View and the Hierarchy
View.

###  5.2 Catalano/Vidro set

To visualize the hierarchy of the Catalano/Vidro network, which is a terrorist
network, the user is required to activate the counter terrorism mode. The idea
behind this mode is based on the study of social networks, we know that there
are three kinds of roles in a network—the _leaders_ , who are the thinking
heads; the _gatekeepers_ , who control the diffusion of information within the
network and the _followers_ who just execute orders. The ones that have the
largest activity within the network are the gatekeepers and therefore, they
have the highest delta efficiency values. On the other side, leaders and
followers have very restricted communications (leaders just issue orders while
followers receive/execute orders) which is the reason why they have very low
delta efficiency values. Past work has shown that leaders try to hide
themselves among followers ML06 ; larsen07  (due to low delta efficiency
values for both) to escape detection. One of the primary goals in hierarchy
detection is to distinguish between followers and leaders. Since there are
three roles that constitute a hierarchy in the social network, we do this by
finding a tree representing this hierarchy such that it reveals the leaders
and the followers.

Our inspiration comes from the fact that the edges of this tree must be part
of the input social network. We know that the gatekeepers (right hands) of the
leaders (boss) are the most critical nodes in the hierarchy. By definition,
they are very close to the leader nodes in the network. We infer the hierarchy
by using the spanning tree of the modified network where each edge is weighted
by the importance of the relationship between the two nodes using delta
efficiency as the importance metric. Thereafter, we classify the different
role types within the influence hierarchy computed from the spanning tree.

Input: A graph $G=(V,E)$, DE $n.\Delta$ of each vertex $n$, the spanning tree
$T$

Output: The root node $boss$ of the hierarchy and an orientation of the
spanning tree $T$

int $number\\_of\\_nodes$ = $3$ / $100$ x $|V|$ ;

Sort($V$, rule $>$, $\Delta$) ;

for _$i$ from $1$ to $number\\_of\\_nodes$_ do table $neighborhood$ =
$V[i]$.getNeighborhood ;

for _$j$ from $1$ to $neighborhood$.size_ do $M[i][j]$ = $neighborhood[j]$;

end end list $result$;

for _$i$ from $1$ to $number\\_of\\_nodes-1$_ do for _$j$ from $(i+1)$ to
$number\\_of\\_nodes$_ do for _$k$ from $1$ to $M[i]$.size_ do for _$l$ from
$1$ to $M[j]$.size_ do if( M[$i$][$k$] == M[$j$][$l$]) then
result.push(M[$i$][$k$]) ; end end end end sort($result$, rule $>$,
$nodes\\_id$) ;

node boss = maxTimeAppears($result$) ;

makeOrientedTree($T$, $boss$) ;

Algorithm 2 Inferring the network hierarchy.

We associate a weight with each edge between two nodes that is the difference
between the delta efficiency value of the connected nodes. A high difference
between delta efficiency values indicate that the two connecting nodes should
not be placed on the same level in the hierarchy so the edge between these
nodes can be removed. We take the absolute value that is inversely
proportional to value associated to the edges as the edge weights for
Kruskal’s Minimum Spanning Tree algorithm to compute the hierarchy tree. The
complete algorithm is listed as 2.

Figure 4: Similarity graph for Catalano/Vidro network over a 10 day period
where blue color represents perfect similarity and yellow represents very low
similarity. (a) suggests high similarity between day 1 to day 6. (b) suggests
a high dissimilarity period between day 7 and 8 marking a major structural
change as between this period, the similarity drops to a very low value. (c)
the similarity between day 8 and 10 is high again representing the stability
of the structure after the change.

From Figure 4, we can easily find that a major structural change occurred
during day 7 and day 8. The terrorist network actually changes their mobile
phones destroying the old communities and forming new ones during day 8 and
day 10. Thus the visualizing the change in the cluster similarity helped us to
identify an interesting information.

Figure 5: Catalano/Vidro Data Set. A cluster found in the period day 1 to day
6 where all the high efficiency nodes labeled 1, 2, 5 communicated with a node
200. The high efficiency nodes represent the right hands of the leader and the
node 200 is in fact the leader of the terrorist network. Since the
communication between the leader and the right hands over a period of time
remains stable, thus the system identified these nodes as a single cluster
where as the people who play the role of followers keep changing as a function
of criminal activity.

Figure 5 represents one of the clusters found in during the period day 1 and
day 6. The highest delta efficiency nodes in this network were identified to
be the nodes labeled 1, 2 and 5. Since we expected that the right hands of the
leader (Boss) are responsible in diffusing information in the terrorist
network, they will have the highest delta efficiency values. This information
was proven to be correct as these nodes indeed represent the right hands of
the Boss. Moreover, we suspected that all the right hands communicate with the
Boss, and over a long period suggesting that there is no change in either the
Boss or his right hands. The only cluster having the right hands and a single
node communicating to all of them was the cluster shown in Figure 5, thus
revealing the identity of the Boss which is the node 200.

Once we have the spanning tree, the next step is to find the leaders (boss) in
the network. We know that the boss has a low delta efficiency value as he
tries to hide himself by communicating less in the network and that he is in
the neighborhood of the gatekeepers (right hands). LM04  suggests that these
right hands have the highest delta efficiency values in the network. But it
may not be true that all the highest valued nodes are the right hands of the
boss. To find the correct number of right hands of the boss we use a heuristic
value of $3\%$ that worked well for the input data set. The idea behind
finding the boss is that we take the $3\%$ nodes having the highest delta
efficiency value and construct a separate neighborhood list for each of these
nodes which contains their immediate neighbors. Once we have these lists, we
count the number of times the elements that appear in both the lists by taking
two lists at a time. For example consider two node lists $list\ 1$ and $list\
2$ that have $3$ elements that are present in both of these lists. We add a
value $1$ as count to each of these elements. We repeat this process for all
the possible combinations of the lists and at the end we come up with the node
that is being communicated the most by the right hands. This node is probably
the boss of the network as we know that the boss communicates a lot with his
right hands. In case if two or more nodes have the same count, we take the
node with the lower delta efficiency value as we know that the boss does not
have a high delta efficiency value.

Once we have a spanning hierarchical tree and the boss of the hierarchy, we
adjust the orientation of the tree, starting from the root (boss) to have an
ordered hierarchy. Given the complexity of our naive implementation of delta
efficiency $O((n+1)(m+n^{2}))$ and the complexity of algorithm 2 is
$O(n^{4})$, the overall worst-case complexity is $O(n^{4})$ where $n$ is the
number of nodes and $m$ is the number of edges in the consensus graph. In
practice, however, the algorithm performs better than the worst-case.

Once the hierarchy is generated, it is displayed in the Hierarchy View window
as shown in Figure 2. As described previously, the nodes with high influence
in the network are placed higher in the tree and the lowest influence nodes
being at the leaves.

##  6 Conclusions and Future Research Directions

In this paper, we have presented a system to analyze dynamic social networks
to detect changes over a time period based on graph discretization and
clustering. We have also presented a method to discover influence hierarchy in
social networks using communication efficiency and minimum spanning tree
algorithm. We have applied our system on two different data sets and obtained
satisfactory results as we were able to correctly identify the time frames
where major structural changes occurred as well as discover the influence
hierarchy of the important people in the social networks. The system has some
obvious limitations. As the number of graphs generated in the discretization
step increases, the systems performance highly depends on the clustering
algorithm used to cluster these individual graphs. If less graphs are
generated, information loss can occur, thus we have a fine

There are several details that we would like to address as part of future
research to improve the overall system. Currently the discretization step
divides the time interval into discrete windows of time which do not overlap.
In case if a structural change occurs in the middle of a time interval, we are
able to detect only the time interval and not the exact time instance. It
would be interesting to analyze the data set if overlapping is allowed to
facilitate the analysis of exact time instances where an event occurred. To
cluster the graph, we have used the strength metric which is based on the
topological information of a network. In the presence of a large number of
attributes, we would like to incorporate other metrics that take into account
these attributes which will certainly improve the quality of clustering. We
use a hierarchical layout to display the influence hierarchy which can very
well be replaced by other layouts such as ego-centric layout which will help
us to focus on individuals and their roles in the entire network. All these
questions present us with new challenges to analyze and understand the
evolving social networks.

## References

  * [1] R. M. Adler.  A dynamic social network software platform for counter-terrorism decision support.  In ISI, pages 47–54. IEEE, 2007.
  * [2] C. C. Aggarwal, J. Han, J. Wang, and P. S. Yu.  A framework for clustering evolving data streams.  In In VLDB, pages 81–92, 2003.
  * [3] D. Auber, Y. Chiricota, F. Jourdan, and G. Melançon.  Multiscale Visualization of Small-World Networks.  In S. C. North and T. Munzner, editors, Proc. of IEEE Information Visualization Symposium, pages 75–81, Seattle, USA, 2003. IEEE Computer Press.
  * [4] A. L. Barabasi and R. Albert.  Emergence of scaling in random networks.  Science, 286(5439):509–512, October 1999.
  * [5] M. Baur, M. Benkert, U. Brandes, S. Cornelsen, M. Gaertler, B. Köpf, J. Lerner, and D. Wagner.  visone - software for visual social network analysis.  In Proc. 9th Intl. Symp. Graph Drawing (GD ’01),LNCS 2265, pages 463–464. Springer-Verlag, 2002.
  * [6] S. Bender-deMoll and D. A. McFarland.  The art and science of dynamic network visualization.  Journal of Social Structure, 7(2), 2006.
  * [7] P. Berkhin.  Survey of clustering data mining techniques.  Technical report, Accrue Software, San Jose, CA, 2002.
  * [8] M. Bilgic, L. Licamele, L. Getoor, and B. Shneiderman.  D-dupe: An interactive tool for entity resolution in social networks.  In Graph Drawing, pages 505–507, 2005.
  * [9] R. Bourqui, F. Gilbert, P. Simonetto, F. Zaidi, U. Sharan, and F. Jourdan.  Detecting structural changes and command hierarchies in dynamic social networks.  In Social Network Analysis and Mining, International Conference on Advances in, pages 83–88, Los Alamitos, CA, USA, 2009. IEEE Computer Society.
  * [10] R. Bourqui, P. Simonetto, and F. Jourdan.  A stable decomposition algorithm for dynamical social network analysis.  Advances in Knowledge Discovery and Management, Studies in Computational Intelligence, Springer., 2009.
  * [11] S. Broh e and J. van Helden.  Evaluation of clustering algorithms for protein-protein interaction networks.  BMC Bioinformatics, 7(1):488, 2006.
  * [12] C. Buchheim, M. Jünger, and S. Leipert.  Improving walker’s algorithm to run in linear time.  In GD ’02: Revised Papers from the 10th International Symposium on Graph Drawing, pages 344–353, London, UK, 2002. Springer-Verlag.
  * [13] S. Chakrabarti, B. Dom, and P. Indyk.  Enhanced hypertext categorization using hyperlinks.  In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 307–318, 1998.
  * [14] J. S. Coleman.  An Introduction to Mathematical Sociology.  Collier-Macmillan, London, UK, 1964.
  * [15] J. Diesner, T. L. Frantz, and K. M. Carley.  Communication networks from the enron email corpus “it’s always about the people. enron is no different”.  In Comput. Math. Organ. Theory, volume 11, pages 201–228, Hingham, MA, USA, 2005. Kluwer Academic Publishers.
  * [16] P. Domingos and M. Richardson.  Mining the network value of customers.  In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 57–66, 2001.
  * [17] S. Eubank, H. Guclu, V. Kumar, M. Marathe, A. Srinivasan, Z. Toroczkai, and N. Wang.  Modelling disease outbreaks in realistic urban social networks.  Nature, 429:180–184, 2004.
  * [18] L. Freeman.  Visualizing social networks.  Journal of Social Structure, 1(1), 2000.
  * [19] L. C. Freeman.  The Development of Social Network Analysis: A Study in the Sociology of Science.  Empirical Press, 2004.
  * [20] P. Gajer and S. G. Kobourov.  GRIP: Graph dRawing with Intelligent Placement.  In Proc. Graph Drawing 2000 (GD’00), pages 222–228, 2000.
  * [21] M. Girvan and M. E. J. Newman.  Community structure in social and biological networks.  Proc. Natl. Acad. Sci. USA, 99:8271–8276, 2002.
  * [22] P. A. Gloor, R. Laubacher, Y. Zhao, and S. B. Dynes.  Temporal visualization and analysis of social networks.  In NAACSOS Conference, June 27 - 29, Pittsburgh PA, North American Association for Computational Social and Organizational Science, 2004\.
  * [23] S. Hachul and M. Junger.  Drawing large graphs with a potential-fieldbased multilevel algorithm.  volume 3383, pages 285– 295, 2004.
  * [24] J. Heer and D. Boyd.  Vizster: Visualizing online social networks.  In INFOVIS ’05: Proceedings of the Proceedings of the 2005 IEEE Symposium on Information Visualization, Washington, DC, USA, 2005. IEEE Computer Society.
  * [25] A. K. Jain, M. N. Murty, and P. J. Flynn.  Data clustering: a review.  ACM Comput. Surv., 31(3):264–323, 1999.
  * [26] T. Jankun-Kelly and K.-L. Ma.  Moiregraphs: Radial focus+context visualization and interaction for graphs with visual nodes.  In T. Munzner and S. North, editors, Proceedings of the 2003 IEEE Symposium on Information Visualization, pages 59–66. IEEE Computer Society TCVG, IEEE Computer Society Press, 2003.
  * [27] P. Kalnis, N. Mamoulis, and S. Bakiras.  On discovering moving clusters in spatio-temporal data.  In SSTD, pages 364–381, 2005.
  * [28] H. Kang, L. Getoor, and L. Singh.  Visual analysis of dynamic group membership in temporal social networks.  SIGKDD Explor. Newsl., 9(2):13–21, 2007.
  * [29] M. Kretzschmar and M. Morris.  Measures of concurrency in networks and the spread of infectious disease.  Math. Biosci., 133:165–195, 1996.
  * [30] J. B. Kruskal.  On the shortest spanning subtree and the traveling salesman problem.  In Proc. of the American Mathematical Society, pages 48–50, 1956\.
  * [31] V. Latora and M. Marchiori.  How Science of Complex Networks can help in developing Strategy against Terrorism.  Chaos, Solitons and Fractals, 20:69–75, 2004.
  * [32] Y. Maeno and Y. Ohsawa.  Analysing covert social network foundation behind terrorism disaster.  Int. J. of Services Sciences, 2:125–141, 2009.
  * [33] N. Memon, D. L. Hicks, and H. L. Larsen.  How investigative data mining can help intelligence agencies to discover dependence of nodes in terrorist networks.  In ADMA ’07: Proc. of the 3rd int. conf. on Advanced Data Mining and Applications, pages 430–441. Springer-Verlag, 2007.
  * [34] N. Memon, D. L. Hicks, H. L. Larsen, and M. A. Uqaili.  Understanding the structure of terrorist networks.  Int. J. of Business Intelligence and Data Mining, 2:401–425, 2007\.
  * [35] N. Memon and H. L. Larsen.  Practical approaches for analysis, visualization and destabilizing terrorist networks.  In ARES ’06: Proc. of the First Int. Conf. on Availability, Reliability and Security, pages 906–913. IEEE Computer Society, 2006.
  * [36] J. Moody, D. Mcfarland, and S. Benderdemoll.  Dynamic network visualization.  American Journal of Sociology, 110(4):1206–1241, January 2005.
  * [37] M. E. Newman.  Scientific collaboration networks. i. network construction and fundamental results.  Phys Rev E Stat Nonlin Soft Matter Phys, 64(1 Pt 2), July 2001.
  * [38] M. E. Newman and M. Girvan.  Finding and evaluating community structure in networks.  Phys Rev E Stat Nonlin Soft Matter Phys, 69(2 Pt 2), February 2004\.
  * [39] A. Rapoport and W. J. Horvath.  A study of a large sociogram.  Behavioral Science, 6(4):279–291, 1961.
  * [40] P. Sarkar and A. W. Moore.  Dynamic social network analysis using latent space models.  SIGKDD Explor. Newsl., 7(2):31–40, 2005.
  * [41] S. E. Schaeffer.  Graph clustering.  Computer Science Review, 1(1):27–64, August 2007.
  * [42] J. P. Scott.  Social Network Analysis: A Handbook.  SAGE Publications, January 2000.
  * [43] Z. Shen, K.-L. Ma, and T. Eliassi-Rad.  Visual analysis of large heterogeneous social networks by semantic and structural abstraction.  IEEE Transactions on Visualization and Computer Graphics, 12(6):1427–1439, 2006.
  * [44] R. C. Tryon.  Cluster analysis. Edwards Brothers, Ann Arbor, Michigan, 1939.
  * [45] V.Martinez, G.Simari, A.Silva, and V.S.Subrahmanian.  The soma terror organization portal (stop): Social network and analytic tools for the real-time analysis of terror groups.  In First Intl. Workshop on Social Computing, Behavioral Modeling and Prediction, 2008.
  * [46] S. Wasserman and K. Faust.  Social Network Analysis: Methods and Applications (Structural Analysis in the Social Sciences).  Cambridge University Press, January 1995.
  * [47] D. J. Watts and S. H. Strogatz.  Collective dynamics of ’small-world’ networks.  Nature, 393:440–442, June 1998.
  * [48] C. C. Yang and T. D. Ng.  Terrorism and crime related weblog social network: Link, content analysis and information visualization.  In ISI, pages 55–58. IEEE, 2007.