Information Technology Reference
In-Depth Information
We can represent the connection among users in social networks as a subset of
U
U
. We define
R
U
U
, using (
u
i
,
u
j
)
R
if
u
i
∈
U
is connected to
∈
u
j
∈
{
(
u
2
,u
1
), (
u
3
,
u
1
),
(
u
3
,
u
2
)
}
describes a social network consists of three users where
u
2
is connected
to
u
1
, and
u
3
is connected to
u
1
and
u
2
. It should be remarked that (
u, u
) could not
belong to
R
for any
u
U
. For example, we see that
U
¼
{u
1
,
u
2
,
u
3
}
and
R
¼
U
.
We say a graph is symmetric when the relations between two users are direc-
tional, that is, (
u
i
,
u
j
)
∈
R
for every element of
R
. Both Facebook
and mixi are symmetric in the relation of social networks, however, Twitter and
e-mail are not symmetric.
R
imples (
u
j
,
u
i
)
∈
∈
3.4.2 Adjacency Matrix
As another representation of the connection of social networks, we can use an
adjacency matrix. The elements of an adjacency matrix for the relation
R
0
@
1
A
a
11
a
12
a
1
n
.
.
.
.
a
21
A
¼
(3.2)
.
.
.
.
.
a
n
1
...
...
a
nn
is defined without loss of generality by
(
1if
ð
u
i
;
u
j
Þ2
R
a
ij
¼
(3.3)
0if
ð
u
i
;
u
j
Þ 2
R
:
for every
i, j
,
n
.
For example, if we take the same social network
U
and
R
in the previous section,
then the adjacency matrix is expressed by
¼
1, 2,
...
0
1
000
100
110
@
A
:
A
¼
(3.4)
3.4.3 Markov Chain Model
The Markov chain model is introduced as a stochastic process in the phenomena of
information diffusion in discrete time steps.
For a social network
U
with
R
, initial data of a state of the users can be written by
n
v
¼ð
v
1
;
v
2
; ...;
v
n
Þ2f
0
;
1
g
;
(3.5)