IEEE Computational Intelligence Magazine - August 2019 - 32

Once an event is detected, WDHG approach suppresses
the bursty keywords at subsequent time intervals.
This characteristic enables other related information
to be more visible and helps in capturing new and
emerging events.
their structures. Canonical order of the
nodes in the graphs is not identical.
Graphs also differ in the number of
nodes. To overcome this issue, we align
the dimensions of adjacent graphs (G i -1
and G i) by regenerating their adjacency matrices in equal dimensions and
canonical order. The procedure of a
WDHG generation is briefly described

in Algorithm 1. Figure 3 illustrates an
example to generate a WDHG from two
adjacent graphs G i -1 and G i . Node
weights are shown in "( )". Edge weights
can be seen beside the edges.
Computational complexity im proves significantly from O (K ;V ;4 ) to
O (K ;V ;2 ) using above mentioned
transformation method, where K = ; G ;

Algorithm 1 Generate Set of WDHG.

input: G = {G 1, G 2, G 3, f, G | P |} a set of temporal graphs generated against a set
of super-documents D t
output: Gh = {G 1h, G 2h, f, G |hG | -1}
foreach G i ! G do
merge set of nodes V G i and V G i +1 by taking union U
regenerate adjacency matrix A for G i using U
regenerate adjacency matrix B for G i +1 using U
calculate difference graph G hi using A, B, V G i, and V G i +1

1
2
3
4
5
6 end

G
2
0
4
0
1

(4)
2

C
0
1
1
2
0

D
A
B
C

A
3
0
6
1

G
4

B
(4) 1

B
0
6
0
4

C
0
1
4
0

1

(2)

1

C
2

A

(2)

A
0
1
2
0
0
0

B
1
0
1
0
4
0

C
2
1
0
0
1
0

D
0
0
0
0
0
0

G
0
4
1
0
0
2

I
0
0
0
0
2
0

A
0
6
1
3
0
0

B
6
0
4
0
0
0

C
1
4
0
0
0
0

-2

(-2)
I

-4

(2)

D
3
0
0
0
0
0

G
0
0
0
0
0
0

I
0
0
0
0
0
0

B

-1

G

3

C

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | AUGUST 2019

(2)

(3) D 3 -1
5

A B C D
A 0 5 -1 3
B 5 0 3 0
C -1 3 0 0
D 3 0 0 0
G 0 -4 -1 0
I 0 0 0 0

FIGURE 3 The example illustrates the process to generate a WDGH.

32

The text stream has diverse contents and
the heartbeat graph inherits the structural and co-occurrence relationship of
a text stream. To understand our event
detection model, let } =G hi where G hi
is i-th heartbeat graph for simplification.
To detect the strong event candidates,
we extract growth factor and aggregated centrality as key features from each WDHG
and perform three experiments to compute corresponding heartbeat scores.

Gi

(-4)

D (3)
(3) 3
A
1
(6) 6
B
C (4)
4

A
B
C
D
G
I

2.3. Event Detection

h

Gi

A (1)

er

O
rd
er
A
B
C
D
G
I

D
0
3
0
0

Gi -1

ed

I

A
0
0
1
0
2

ed

(2)

B
0
4
0
1
1

O
rd

I
0
2
0
0
0

I
G
B
A
C

G I
0 0
-4 0
-1 0
0 0
0 -2
-2 0

is the number of graphs in the graph
series G.
One of the inherent characteristics of
WDHG is to suppress and handle bias in
the data caused by the burstiness of dominating topics. Each WDHG is formulated by estimating the displaced temporal
frequency of nodes and edges between
each pair of graphs G i -1 and G i to highlight other event-related information,
which might also be important but less
frequent at the same time. Algorithm 1
calculates the change in the corresponding pair of graphs G i -1 and G i . It generates a WDHG G hi by assigning new
weights to all the nodes and edges. The
graph series G is transformed into
WDHG series Gh in a streaming fashion
without affecting the temporal alignment
of the data. Furthermore, these WDHGs
are used to detect emerging events at
precise time descriptions. The methodology of the event detection process is
described in the next section.

2.3.1. Growth Factor Based
In the first experiment, we use growth
factor GF (}) to compute the heartbeat.
GF (}) is an accumulated score of node
weights in a WDHG } which shows the
intensity of drift in topics and their popularity in the text stream. It also shows
how previously observed topics are
trending, in terms of popularity and if
new topics are emerging at the time
interval t i compared to t i -1 (1).
;V } ;

GF (}) = / j(v k} ),

(1)

k =1

where j(v }k ) is the kth node weight
which represents the displaced temporal
IEEE Computational Intelligence Magazine - August 2019

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - August 2019
