# Social Network Analysis Based on Network Motifs

Authors: Xu Hong-lin; Yan Han-bing; Gao Cui-fang; Zhu Ping
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Based on the community structure characteristics, theory, and methods of frequent subgraph mining, network motifs findings are firstly introduced into social network analysis; the tendentiousness evaluation function and the importance evaluation function are proposed for effectiveness assessment. Compared with the traditional way based on nodes centrality degree, the new approach can be used to analyze the properties of social network more fully and judge the roles of the nodes effectively. In application analysis, our approach is shown to be effective.


---

## Body

## 1. Introduction

A large number of systems in the real world exist as networks, such as social networks (coauthor network, criminal networks, etc.), biological networks (protein interaction networks, metabolic networks, etc.), and technology networks (electricity networks, the Internet, etc.) [1–12]. In order to reveal their structure and principle, Milo et al. first proposed the concept of “network motifs,” which can be defined as patterns of interconnections occurring in complex networks at numbers that are significantly higher than those in randomized network [13]. Later, research on network motifs has been developed extensively. Kim et al. defined biological network motifs as biologically significant subgraphs [14]. Farina et al. identified regulatory network motifs from gene expression data, and they proposed the corresponding algorithm [15]. In order to specify network motifs, Ohnishi et al. analyzed an interfirm network consisting of about one million firms and four million directed links [16].The study of social networks has always been a hot research topic. In order to judge the importance of nodes, the staple methods of traditional social network analysis are basing on the calculation of the centrality of nodes in network, [17, 18]. In recent years, various new methods are introduced into social network analysis; network motif is an important kind of them [19, 20]. Analyzing motifs for the large social networks derived from email communication firstly, Juszczyszyn found that the distribution of motifs in all analyzed real social networks is similar and can be treated as the network fingerprint. This property is most distinctive for stronger human relationships [21, 22].In this paper, we introduce network motifs to develop a set of network analysis methods, which is different from the traditional social network analysis, and also illustrate its application.


## 2. Research Methods

### 2.1. Directed Graph and Point Centrality

A network withn nodes is denoted by G
=
(
V
,
E
), where V
=
{
v
i
∣
i
=
1,2
,
…
,
n
} is node set, E
=
{
〈
v
i
,
v
j
〉
∣
v
i
is  the  start  node
,
v
j
is  the  end  node
,
and
i
,
j
=
1,2
,
…
,
n
}  is edge set. A
=
(
a
i
j
)
n
×
n is  adjacency  matrix of G, of which the elements are as follows:
(1)
a
i
j
=
{
1
,
〈
v
i
,
v
j
〉
∈
E
,
0
,
〈
v
i
,
v
j
〉
∉
E
,
where i
,
j
=
1,2
,
…
,
n.The centrality analysis is the staple method of traditional social network analysis [17, 18]. In a network, if there are direct links between an actor and other actors, this actor resides in the centre of the network, having more “power” [17]. The importance of a node, point centrality, can be measured by the number of contacted nodes [18]. Based on the adjacency matrix, the formula of point centrality of node v
i is as follows:
(2)
C
(
v
i
)
=
c
i
=
∑
j
=
1
n
a
i
j
+
∑
k
=
1
n
a
k
i
,
where i
=
1,2
,
…
,
n.


### 2.2. Network Motifs Finding

#### 2.2.1. Frequent Graph

Frequent subgraph mining is an important method of network information mining. Frequent subgraph mining algorithms are divided into breadth-first search (BFS) algorithm and depth-first search (DFS) algorithm based on subgraph search path [23]. As a breadth-first search algorithm, Apriori graph mining (AGM) algorithm is an early adopter of Apriori idea. AGM algorithm takes an adjacency matrix to represent the graph. Then it generates code based on adjacency matrix and takes minimum coding as unique identification for the graph in order to solve NP problem of subgraph isomorphism [24].The graph which is constituted byK node set V
s
=
{
v
s
1
,
v
s
2
,
…
,
v
s
k
} and edge set E
s
=
{
〈
v
s
i
,
v
s
j
〉
∣
v
s
i
,
v
s
j
∈
V
s
} is a subgraph of G. Let S
G
s
=
G
(
V
s
)
=
(
V
s
,
E
s
). Furthermore, the node set of subgraph S
G
s is denoted as V
s
=
V
(
S
G
s
).Based on the adjacency matrix of a subgraph, the maximum encoding is obtained as unique identification of the subgraph. AGM algorithm is used to mine frequent subgraphs based on the maximum encoding.


#### 2.2.2. Random Network Model

In typical network motifs finding algorithms, random network model maintains the degree sequence of the real network very well [25]. Exchange algorithm is an algorithm for generating random network according to degree sequence, which is as follows [26].Algorithm A.Input: degree sequence
Output: random network
Step 1: Construct a network according to degree sequence.
Step 2: Randomly select a pair of edges (e.g.,A
→
B,C
→
D).
Step 3: Carry out the Monte Carlo exchange (A
→
D,C
→
B).
Step 4: Cancel the exchange if the exchange has led to multiple edges or loops.
Step 5: Repeat until reaching the target number of times.In this way, a set of random networks with the same degree sequence as G can be obtained.


#### 2.2.3. Statistical Significance of Network Motifs

Network motifs are frequent subgraphs with special statistical significance, which have some special functions in the network. Network motifs satisfy the following conditions: occurrence of the subgraph in real network is not less than a minimum and is significantly higher than their occurrence in random network [13, 27].The statistical significance of network motifs is denoted byZ
-
s
c
o
r
e:
(3)
Z
=
N
real
-
〈
N
rand
〉
σ
rand
,
where N
real denotes the occurrences of a subgraph in real network and 〈
N
rand
〉 and σ
rand denote mean and standard deviation of the occurrences of the subgraph in random networks.


### 2.3. Frequency Matrix

The nodes of a network always have a lot of roles, such as teacher and student. Most social networks can be simulated by role network model (RNM). The role set is denoted byR
=
{
R
i
=
1,2
,
…
,
m
}, where m is the number of roles. The set of nodes whose role is R
k
(
k
=
1,2
,
…
,
m) is denoted by V
k
R, so the set of V
k
R is denoted by V
R
=
{
V
1
R
,
V
2
R
,
…
,
V
m
R
}. M
S
G denotes the set of subgraphs whose structure is the same as the network motifs in the network.In order to determine the role tendentiousness of the unknown role nodes, we can count the frequency of the unknown role nodes occurring in different network motifs, respectively, through the composition of nodes in network motifs, which contain different known role nodes.Based on network motifs, frequency matrixF
=
(
f
i
j
)
n
×
m is obtained. The elements f
i
j of F denotes the total occurrences of node v
i in the network motifs that contain the known role nodes, whose role is R
j.The algorithm for calculating frequency matrix is as follows.Algorithm B.Input:V, V
R, M
S
G
Output:F
Step 1: For anyi
∈
{
1,2
,
…
,
n
}, for any j
∈
{
1,2
,
…
,
n
}
f
i
j
⇐
0.
Step 2: For anyM
S
G
i
∈
M
S
G, for any V
j
R
∈
V
R, if V
(
M
S
G
i
)
∩
V
j
R
≠
∅, then for any v
i
k
∈
M
S
G
i,f
i
k
j
=
f
i
k
j
+
1.
Step 3: OutputF
=
(
f
i
j
)
n
×
m.
Step 4: End.


### 2.4. Evaluation Function

#### 2.4.1. Tendentiousness Evaluation Function (TEF)

Based on frequency matrixF, the tendentiousness of node v
i with respect to role R
j is evaluated by TEF.Definition 1.
The TEF valuep
i
j is defined by
(4)
p
i
j
=
P
(
v
i
,
R
j
)
=
{
1
,
R
(
v
i
)
=
R
j
,
0
,
R
(
v
i
)
∈
R
,
R
(
v
i
)
≠
R
j
,
f
i
j
∑
k
=
1
n
f
k
j
×
f
i
j
∑
k
=
1
m
f
i
k
R
(
v
i
)
∉
R
,
where 0
≤
p
i
j
≤
1,  i
=
1,2
,
…
,
n, and  j
=
1,2
,
…
,
n. Obviously, the greater p
i
j, the greater the tendentiousness of node v
i with respect to role R
j.


#### 2.4.2. Importance Evaluation Function (IEF)

Based on point centrality and TEF, the importance of nodev
i with respect to role R
j in the network is evaluated by IEF.Definition 2.
The IEF valueS
i
j is defined by
(5)
S
i
j
=
S
(
v
i
,
R
j
)
=
c
i
×
p
i
j
=
f
i
j
∑
k
=
1
n
f
k
j
×
f
i
j
∑
k
=
1
m
f
i
k
.
The normalized form is
(6)
x
i
j
=
X
(
v
i
,
R
j
)
=
S
(
v
i
,
R
j
)
-
min
⁡
1
≤
i
≤
n
⁡
(
S
(
v
i
,
R
j
)
)
max
⁡
1
≤
i
≤
n
⁡
(
S
(
v
i
,
R
j
)
)
-
min
⁡
1
≤
i
≤
n
⁡
(
S
(
v
i
,
R
j
)
)
,
where 0
≤
x
i
j
≤
1,  i
=
1,2
,
…
,
n,  and j
=
1,2
,
…
,
n. The greater x
i
j, obviously, the greater the importance of node v
i with respect to role R
j in the network.


## 2.1. Directed Graph and Point Centrality

A network withn nodes is denoted by G
=
(
V
,
E
), where V
=
{
v
i
∣
i
=
1,2
,
…
,
n
} is node set, E
=
{
〈
v
i
,
v
j
〉
∣
v
i
is  the  start  node
,
v
j
is  the  end  node
,
and
i
,
j
=
1,2
,
…
,
n
}  is edge set. A
=
(
a
i
j
)
n
×
n is  adjacency  matrix of G, of which the elements are as follows:
(1)
a
i
j
=
{
1
,
〈
v
i
,
v
j
〉
∈
E
,
0
,
〈
v
i
,
v
j
〉
∉
E
,
where i
,
j
=
1,2
,
…
,
n.The centrality analysis is the staple method of traditional social network analysis [17, 18]. In a network, if there are direct links between an actor and other actors, this actor resides in the centre of the network, having more “power” [17]. The importance of a node, point centrality, can be measured by the number of contacted nodes [18]. Based on the adjacency matrix, the formula of point centrality of node v
i is as follows:
(2)
C
(
v
i
)
=
c
i
=
∑
j
=
1
n
a
i
j
+
∑
k
=
1
n
a
k
i
,
where i
=
1,2
,
…
,
n.


## 2.2. Network Motifs Finding

### 2.2.1. Frequent Graph

Frequent subgraph mining is an important method of network information mining. Frequent subgraph mining algorithms are divided into breadth-first search (BFS) algorithm and depth-first search (DFS) algorithm based on subgraph search path [23]. As a breadth-first search algorithm, Apriori graph mining (AGM) algorithm is an early adopter of Apriori idea. AGM algorithm takes an adjacency matrix to represent the graph. Then it generates code based on adjacency matrix and takes minimum coding as unique identification for the graph in order to solve NP problem of subgraph isomorphism [24].The graph which is constituted byK node set V
s
=
{
v
s
1
,
v
s
2
,
…
,
v
s
k
} and edge set E
s
=
{
〈
v
s
i
,
v
s
j
〉
∣
v
s
i
,
v
s
j
∈
V
s
} is a subgraph of G. Let S
G
s
=
G
(
V
s
)
=
(
V
s
,
E
s
). Furthermore, the node set of subgraph S
G
s is denoted as V
s
=
V
(
S
G
s
).Based on the adjacency matrix of a subgraph, the maximum encoding is obtained as unique identification of the subgraph. AGM algorithm is used to mine frequent subgraphs based on the maximum encoding.


### 2.2.2. Random Network Model

In typical network motifs finding algorithms, random network model maintains the degree sequence of the real network very well [25]. Exchange algorithm is an algorithm for generating random network according to degree sequence, which is as follows [26].Algorithm A.Input: degree sequence
Output: random network
Step 1: Construct a network according to degree sequence.
Step 2: Randomly select a pair of edges (e.g.,A
→
B,C
→
D).
Step 3: Carry out the Monte Carlo exchange (A
→
D,C
→
B).
Step 4: Cancel the exchange if the exchange has led to multiple edges or loops.
Step 5: Repeat until reaching the target number of times.In this way, a set of random networks with the same degree sequence as G can be obtained.


### 2.2.3. Statistical Significance of Network Motifs

Network motifs are frequent subgraphs with special statistical significance, which have some special functions in the network. Network motifs satisfy the following conditions: occurrence of the subgraph in real network is not less than a minimum and is significantly higher than their occurrence in random network [13, 27].The statistical significance of network motifs is denoted byZ
-
s
c
o
r
e:
(3)
Z
=
N
real
-
〈
N
rand
〉
σ
rand
,
where N
real denotes the occurrences of a subgraph in real network and 〈
N
rand
〉 and σ
rand denote mean and standard deviation of the occurrences of the subgraph in random networks.


## 2.2.1. Frequent Graph

Frequent subgraph mining is an important method of network information mining. Frequent subgraph mining algorithms are divided into breadth-first search (BFS) algorithm and depth-first search (DFS) algorithm based on subgraph search path [23]. As a breadth-first search algorithm, Apriori graph mining (AGM) algorithm is an early adopter of Apriori idea. AGM algorithm takes an adjacency matrix to represent the graph. Then it generates code based on adjacency matrix and takes minimum coding as unique identification for the graph in order to solve NP problem of subgraph isomorphism [24].The graph which is constituted byK node set V
s
=
{
v
s
1
,
v
s
2
,
…
,
v
s
k
} and edge set E
s
=
{
〈
v
s
i
,
v
s
j
〉
∣
v
s
i
,
v
s
j
∈
V
s
} is a subgraph of G. Let S
G
s
=
G
(
V
s
)
=
(
V
s
,
E
s
). Furthermore, the node set of subgraph S
G
s is denoted as V
s
=
V
(
S
G
s
).Based on the adjacency matrix of a subgraph, the maximum encoding is obtained as unique identification of the subgraph. AGM algorithm is used to mine frequent subgraphs based on the maximum encoding.


## 2.2.2. Random Network Model

In typical network motifs finding algorithms, random network model maintains the degree sequence of the real network very well [25]. Exchange algorithm is an algorithm for generating random network according to degree sequence, which is as follows [26].Algorithm A.Input: degree sequence
Output: random network
Step 1: Construct a network according to degree sequence.
Step 2: Randomly select a pair of edges (e.g.,A
→
B,C
→
D).
Step 3: Carry out the Monte Carlo exchange (A
→
D,C
→
B).
Step 4: Cancel the exchange if the exchange has led to multiple edges or loops.
Step 5: Repeat until reaching the target number of times.In this way, a set of random networks with the same degree sequence as G can be obtained.


## 2.2.3. Statistical Significance of Network Motifs

Network motifs are frequent subgraphs with special statistical significance, which have some special functions in the network. Network motifs satisfy the following conditions: occurrence of the subgraph in real network is not less than a minimum and is significantly higher than their occurrence in random network [13, 27].The statistical significance of network motifs is denoted byZ
-
s
c
o
r
e:
(3)
Z
=
N
real
-
〈
N
rand
〉
σ
rand
,
where N
real denotes the occurrences of a subgraph in real network and 〈
N
rand
〉 and σ
rand denote mean and standard deviation of the occurrences of the subgraph in random networks.


## 2.3. Frequency Matrix

The nodes of a network always have a lot of roles, such as teacher and student. Most social networks can be simulated by role network model (RNM). The role set is denoted byR
=
{
R
i
=
1,2
,
…
,
m
}, where m is the number of roles. The set of nodes whose role is R
k
(
k
=
1,2
,
…
,
m) is denoted by V
k
R, so the set of V
k
R is denoted by V
R
=
{
V
1
R
,
V
2
R
,
…
,
V
m
R
}. M
S
G denotes the set of subgraphs whose structure is the same as the network motifs in the network.In order to determine the role tendentiousness of the unknown role nodes, we can count the frequency of the unknown role nodes occurring in different network motifs, respectively, through the composition of nodes in network motifs, which contain different known role nodes.Based on network motifs, frequency matrixF
=
(
f
i
j
)
n
×
m is obtained. The elements f
i
j of F denotes the total occurrences of node v
i in the network motifs that contain the known role nodes, whose role is R
j.The algorithm for calculating frequency matrix is as follows.Algorithm B.Input:V, V
R, M
S
G
Output:F
Step 1: For anyi
∈
{
1,2
,
…
,
n
}, for any j
∈
{
1,2
,
…
,
n
}
f
i
j
⇐
0.
Step 2: For anyM
S
G
i
∈
M
S
G, for any V
j
R
∈
V
R, if V
(
M
S
G
i
)
∩
V
j
R
≠
∅, then for any v
i
k
∈
M
S
G
i,f
i
k
j
=
f
i
k
j
+
1.
Step 3: OutputF
=
(
f
i
j
)
n
×
m.
Step 4: End.


## 2.4. Evaluation Function

### 2.4.1. Tendentiousness Evaluation Function (TEF)

Based on frequency matrixF, the tendentiousness of node v
i with respect to role R
j is evaluated by TEF.Definition 1.
The TEF valuep
i
j is defined by
(4)
p
i
j
=
P
(
v
i
,
R
j
)
=
{
1
,
R
(
v
i
)
=
R
j
,
0
,
R
(
v
i
)
∈
R
,
R
(
v
i
)
≠
R
j
,
f
i
j
∑
k
=
1
n
f
k
j
×
f
i
j
∑
k
=
1
m
f
i
k
R
(
v
i
)
∉
R
,
where 0
≤
p
i
j
≤
1,  i
=
1,2
,
…
,
n, and  j
=
1,2
,
…
,
n. Obviously, the greater p
i
j, the greater the tendentiousness of node v
i with respect to role R
j.


### 2.4.2. Importance Evaluation Function (IEF)

Based on point centrality and TEF, the importance of nodev
i with respect to role R
j in the network is evaluated by IEF.Definition 2.
The IEF valueS
i
j is defined by
(5)
S
i
j
=
S
(
v
i
,
R
j
)
=
c
i
×
p
i
j
=
f
i
j
∑
k
=
1
n
f
k
j
×
f
i
j
∑
k
=
1
m
f
i
k
.
The normalized form is
(6)
x
i
j
=
X
(
v
i
,
R
j
)
=
S
(
v
i
,
R
j
)
-
min
⁡
1
≤
i
≤
n
⁡
(
S
(
v
i
,
R
j
)
)
max
⁡
1
≤
i
≤
n
⁡
(
S
(
v
i
,
R
j
)
)
-
min
⁡
1
≤
i
≤
n
⁡
(
S
(
v
i
,
R
j
)
)
,
where 0
≤
x
i
j
≤
1,  i
=
1,2
,
…
,
n,  and j
=
1,2
,
…
,
n. The greater x
i
j, obviously, the greater the importance of node v
i with respect to role R
j in the network.


## 2.4.1. Tendentiousness Evaluation Function (TEF)

Based on frequency matrixF, the tendentiousness of node v
i with respect to role R
j is evaluated by TEF.Definition 1.
The TEF valuep
i
j is defined by
(4)
p
i
j
=
P
(
v
i
,
R
j
)
=
{
1
,
R
(
v
i
)
=
R
j
,
0
,
R
(
v
i
)
∈
R
,
R
(
v
i
)
≠
R
j
,
f
i
j
∑
k
=
1
n
f
k
j
×
f
i
j
∑
k
=
1
m
f
i
k
R
(
v
i
)
∉
R
,
where 0
≤
p
i
j
≤
1,  i
=
1,2
,
…
,
n, and  j
=
1,2
,
…
,
n. Obviously, the greater p
i
j, the greater the tendentiousness of node v
i with respect to role R
j.


## 2.4.2. Importance Evaluation Function (IEF)

Based on point centrality and TEF, the importance of nodev
i with respect to role R
j in the network is evaluated by IEF.Definition 2.
The IEF valueS
i
j is defined by
(5)
S
i
j
=
S
(
v
i
,
R
j
)
=
c
i
×
p
i
j
=
f
i
j
∑
k
=
1
n
f
k
j
×
f
i
j
∑
k
=
1
m
f
i
k
.
The normalized form is
(6)
x
i
j
=
X
(
v
i
,
R
j
)
=
S
(
v
i
,
R
j
)
-
min
⁡
1
≤
i
≤
n
⁡
(
S
(
v
i
,
R
j
)
)
max
⁡
1
≤
i
≤
n
⁡
(
S
(
v
i
,
R
j
)
)
-
min
⁡
1
≤
i
≤
n
⁡
(
S
(
v
i
,
R
j
)
)
,
where 0
≤
x
i
j
≤
1,  i
=
1,2
,
…
,
n,  and j
=
1,2
,
…
,
n. The greater x
i
j, obviously, the greater the importance of node v
i with respect to role R
j in the network.


## 3. Application Analysis

The Intergalactic Crime Modelers (ICM) is investigating a conspiracy to commit a criminal act. The case involves 83 members and 400 messages between these people, as shown in Figure1. As priorly known in [28], Jean, Alex, Elsie, Paul, Ulf, Yao, Harvey are conspirators, Darlene, Tran, Jia, Ellin, Gard, Chris, Paige, Este are nonconspirators.Figure 1
Visualized of the network model of the 83 people (nodes) and 400 messages between these people (links).Now, we analyze the set of prior conspirator and the set of prior non-conspirator by using the theory and methods of network motifs.Firstly, letR
1 be “conspirator” and let R
2 be “non-conspirator”. Then the links are divided into two categories, of which daily topic is denoted by topic 1, and conspiracy topic is denoted by topic 2.Based on adjacency matrix of the network, point centrality of nodes is calculated by using formulas (2) as shown in Table 1. The point centrality reflects the influence of a node in the network, which means the larger point centrality a criminal node have, the bigger negative impact on the network will occur. Therefore, ICM should focus on high-ranking members in Table 1.Table 1
Point centrality.
Name
c
i
Name
c
i
Name
c
i
Name
c
i
Name
c
i
Gretchen
29
Lois
14
Dwight
11
Cory
6
Tran
3
Sherri
26
Donald
14
Marion
11
Jia
6
Quan
3
Jerome
23
Neal
14
Malcolm
11
Shelley
6
Olina
3
Neal
22
Wayne
14
Karen
11
Wesley
6
Phille
2
Julia
22
Marian
14
Yao
10
Chris
6
Cole
2
Franklin
21
Crystal
14
Douglas
10
Este
5
Bariol
2
Paige
21
Kristine
14
Claire
10
Hark
5
Le
2
Elsie
20
Beth
14
Jean
10
Mai
5
Darol
2
Darlene
18
Sandy
14
Christina
9
Lars
5
Lao
2
Patricia
18
Dolores
14
Priscilla
9
Gerry
4
Cha
2
Paul
17
Patrick
14
Reni
8
Ellin
4
Vind
2
Kristina
17
William
13
Ulf
8
Kim
4
Carina
1
Alex
16
Francis
13
Harvey
8
Seeni
3
Sheng
1
Hazel
16
Beth
12
Erica
8
Fanti
3
Chara
1
Marcia
15
Stephanie
12
Jerome
8
Gard
3
Dayi
0
Eric
15
Katherine
11
Han
7
Andra
3
Gretchen
15
Elsie
11
Louis
7
Melia
3According to the method in Section2.2, frequent subgraphs and network motifs of the network are obtained, as shown in Table 2 (example).Table 2
The sample of frequent subgraph and network motifs.
Scale
ID
Structure
N
real
Z
Scale
ID
Structure
N
real
Z
2
S1
230
1.1609
4
M4
30
5.4641
2
S2
10
3.6995
4
M5
30
5.7152
3
M1
15
5.8795
5
M6
136
5.7783
4
M2
38
9.7047
5
M7
126
9.4614
4
M3
36
8.1592
5
M8
102
8.3725
Note of figure: S1-2 are not network motifs (Z
<
5); M1-8 are network motifs (Z
>
5), which are structure module with special features (the minimum of Z-score is 5).Depending on the network motifs, frequency matrix is obtained by applying Algorithm B. Based on the evaluation functions TEF and IEF, the priority list of criminal tend and the priority list for key monitoring are obtained, as shown respectively, in Tables3 and 4.Table 3
Priority list of criminal tend.
Name
p
i
1
p
i
2
Name
p
i
1
p
i
2
Name
p
i
1
p
i
2
Jean
1
0
Donald
0.0069
0.0064
Gerry
0.0001
0.0038
Alex
1
0
Shelley
0.0065
0.0051
Franklin
0.0001
0.0060
Elsie
1
0
Dwight
0.0061
0.0100
Phille
0
0
Paul
1
0
Louis
0.0057
0.0005
Cole
0
0
Ulf
1
0
Beth
0.0054
0.0015
Bariol
0
0
Yao
1
0
Karen
0.0054
0.0231
Cory
0
0
Harvey
1
0
Kim
0.0051
0.0007
Quan
0
0
Marcia
0.0316
0.0059
Kristina
0.0042
0.0000
Mai
0
0
Stephanie
0.0229
0.0178
Han
0.0033
0.0003
Le
0
0
Jerome
0.0210
0.0068
Lars
0.0031
0.0000
Darol
0
0
Crystal
0.0196
0.0197
Erica
0.0031
0.0014
Sheng
0
0
Priscilla
0.0173
0.0016
Wayne
0.0030
0.0249
Cha
0
0
Neal
0.0153
0.0100
Carina
0.0027
0.0001
Olina
0
0
William
0.0141
0.0014
Elsie
0.0027
0.0159
Chara
0
0
Sherri
0.0140
0.0072
Gretchen
0.0025
0.0075
Vind
0
0
Douglas
0.0129
0.0054
Marion
0.0024
0.0052
Dayi
0
0
Patrick
0.0111
0.0005
Katherine
0.0023
0.0049
Seeni
0
0.0005
Gretchen
0.0098
0.0180
Kristine
0.0023
0.0303
Lao
0
0.0018
Dolores
0.0096
0.0024
Francis
0.0016
0.0001
Fanti
0
0.0023
Julia
0.0096
0.0033
Eric
0.0014
0.0007
Darlene
0
1
Patricia
0.0089
0.0106
Sandy
0.0007
0.0022
Tran
0
1
Jerome
0.0088
0.0001
Melia
0.0004
0
Jia
0
1
Christina
0.0086
0.0048
Wesley
0.0004
0
Ellin
0
1
Neal
0.0085
0.0006
Claire
0.0003
0.0012
Gard
0
1
Reni
0.0084
0.0010
Marian
0.0003
0.0026
Chris
0
1
Lois
0.0080
0.0055
Hark
0.0002
0.0002
Paige
0
1
Hazel
0.0078
0.0084
Malcolm
0.0001
0.0006
Este
0
1
Beth
0.0074
0.0523
Andra
0.0001
0.0014Table 4
Priority list for key monitoring.
ID
Name
x
i
1
ID
Name
x
i
1
ID
Name
x
i
1
8
Jean
1.0000
2
Donald
0.0036
78
Gerry
0.0000
44
Alex
0.8500
17
Shelley
0.0035
73
Franklin
0.0000
22
Elsie
0.8000
29
Dwight
0.0034
82
Phille
0
68
Paul
0.5000
83
Louis
0.0034
81
Cole
0
19
Ulf
0.5000
6
Beth
0.0030
80
Bariol
0
55
Yao
0.4000
30
Karen
0.0021
79
Cory
0
50
Harvey
0.4000
47
Kim
0.0020
77
Quan
0
35
Marcia
0.0241
36
Kristina
0.0020
76
Mai
0
28
Stephanie
0.0237
5
Han
0.0019
75
Le
0
4
Jerome
0.0182
20
Lars
0.0016
72
Darol
0
33
Crystal
0.0143
38
Erica
0.0015
69
Sheng
0
31
Priscilla
0.0138
14
Wayne
0.0013
66
Cha
0
21
Neal
0.0137
43
Carina
0.0012
65
Olina
0
32
William
0.0107
40
Elsie
0.0012
64
Chara
0
16
Sherri
0.0106
70
Gretchen
0.0012
63
Vind
0
18
Douglas
0.0094
12
Marion
0.0010
62
Dayi
0
51
Patrick
0.0092
34
Katherine
0.0010
60
Seeni
0
45
Gretchen
0.0080
23
Kristine
0.0010
59
Lao
0
37
Dolores
0.0078
61
Francis
0.0008
58
Fanti
0
7
Julia
0.0078
13
Eric
0.0005
57
Darlene
0
11
Patricia
0.0067
27
Sandy
0.0002
56
Tran
0
41
Jerome
0.0064
74
Melia
0.0001
54
Jia
0
9
Christina
0.0062
26
Wesley
0.0001
53
Ellin
0
46
Neal
0.0056
24
Claire
0.0001
52
Gard
0
42
Reni
0.0048
25
Marian
0.0001
49
Chris
0
39
Lois
0.0045
10
Hark
0.0001
3
Paige
0
48
Hazel
0.0039
67
Malcolm
0.0001
1
Este
0
15
Beth
0.0038
71
Andra
0.0000By comparing and analyzing, the “network motifs” offer a much more comprehensive way to analyze social networks; the high-ranking members having both higher point centrality and more criminal tend in Tables3 and 4 are more suspect than others, so ICM should monitor them. Our research confirmed that the method is suitable in social network and the results are reliable.


## 4. Conclusions

In this paper, we developed a set of network analysis methods based on the theory and methods of social network analysis, frequent subgraph mining, network motifs, and so forth, which is different from the traditional social network analysis. In application analysis, a series of priority lists are obtained based on the evaluation functions. The priority lists reflect network information effectively, which is of great reference value for ICM.Based on the study on node connection relationship of social networks, a follow-up study will involve more attention to structural relationship with more practical value.



---

*Source: 874708-2014-02-16.xml*