# Crowd Sensing Based Burst Computing of Events Using Social Media

Authors: Zheng Xu; Yunhuai Liu; Lin Mei; Hui Zhang; Chuanping Hu
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

With the popularity of web, the internet is becoming a major information provider and poster of an event due to its real-time, open, and dynamic features. In this paper, crowd sensing based burst computation algorithm of a web event is developed in order to let the people know a web event clearly and help the social group or government process the events effectively. Different temporal features of web events are developed to provide the basics for the proposed computation algorithm. The burst power is presented to integrate the above temporal features of an event. Empirical experiments on real datasets including Google Zeitgeist and Google Trends show that the number of web pages and the average clustering coefficient can be used to detect events. The evaluations on real dataset show that the proposed function integrating the number of web pages and the average clustering coefficient can be used for event detection efficiently and correctly.


---

## Body

## 1. Introduction

Crowd sensing is a process of acquisition, integration, and analysis of big and heterogeneous data generated by a diversity of sources in urban spaces, such as sensors, devices, vehicles, buildings, and human. With the help of cloud computing [1–4], internet of things [5–7], and Big Data [8, 9], crowd sensing connects unobtrusive and ubiquitous sensing technologies, advanced data management and analytics models, and novel visualization methods to create solutions that improve urban environment, human life quality, and city operation systems. Current research in crowd sensing addresses the following issues: crowd sensing as a novel methodology for user-centered research; development of new services and applications based on human sensing, computation, and problem solving; engineering of improved crowd sensing platforms including quality control mechanisms; incentive design of work; usage of crowd sensing for professional business; and theoretical frameworks for evaluation. Nowadays, no countries, no communities, and no person are immune to emergency events [10]. An emergency event is a sudden, urgent, usually unexpected incident or occurrence that requires an immediate reaction or assistance for emergency situations faced by social group (e.g., the corporations) or the recipients of public assistance [11]. How to prepare for, respond to, and recover from the emergency events is important. An apparent choice for processing an emergency event is to analyze its related information. Due to the popularity of the web, most emergency events are reported in the form of web resources. Particularly, with the development of the social media, people can get/post more and more information of emergency events from/to the web. In fact, a web user can be seen as a sensor of an emergency event. For example, if a user makes a post in microblogs or BBS about an earthquake occurrence, then she/he can be seen as an “earthquake sensor.” Web can be seen as a sensor receiver. In this paper, we call the web users as “social sensors.” In our view, using related web resources as crowd sensing to analyze emergency events has the following advantages.(1) Real-Time of Web. Web can provide related information immediately after an emergency event happens, which is associated with the sudden feature of emergency events. Traditional media such as newspapers and magazines cannot report an emergency event immediately. On the contrary, web can release this issue properly. For example, from some reports, the time when Chinese web users know the September 11 attacks is only 5 minutes later than the president of the United States [12, 13]. Recently, with the rapid development of social media such as Twitter and Facebook, web becomes an important events’ information provider more than ever [14].(2) Free Spread of Web. The free spread of information by web can provide comprehensive perspective of emergency events. Traditional media usually give some dedicated points such as expert opinions to public. In other words, traditional media usually try to conclude some emergency events rather than reporting them. Different from the traditional media, web can provide different perspectives of an emergency event. Different users can give their own opinions about an emergency event. The open feature of web ensures that users know the different aspects of opinions about an emergency event.(3) Constant Change of Web. The dynamic feature of web information can keep up with the evolution of emergency events. Of course, an emergency event is not static. On the contrary, the information of it may change with the time. In some studies [15], the change of an event is named event evolution. The event evolution generates a large volume of temporal data. For example, when you search “Moammar Gadhafi” in Google, the total number of news about it in 24/10/2011 is 23,400. These large numbers of information should have an appropriate intermediate to support them. Besides the large volume of data, the information of an emergency event updates quickly. For example, the increased number of the news is 22,800 in 25/10/2011, which is almost equal to that in the past. Web as a live and active corpus can keep up with the evolution of emergency events.In a web environment, web pages come from one or more sources. Event detection is the task of capturing the first web page that mentions previously unseen events. This task has practical applications in several domains including intelligence gathering, financial market analyses, and news analyses, where useful information is buried in a large amount of data that grows rapidly with time. The recently released Google Flu (http://www.google.org/flutrends/) Trends showcases an important application on estimating flu epidemics based on queries received from massive web users. The US government is building a massive computer system that can monitor news, blogs, and emails for antiterrorism purposes [16], and event detection is an essential component of this system. In this paper, we introduce a new web mining task—burst power computation of emergency events using crowd sensing. Given an emergency event, the related web pages can be found, examples of web news, microblogs, and forums. Based on the semantics of these web pages formed by social sensors, the temporal features of an event are given. And then, the burst power is computed. The major contributions of this paper are as follows.(1)
In this work, we define the novel problem of computing the burst power of an emergency event. The temporal features of an emergency event imaged on the web are built, which integrate the number of the increased web pages, the number of increased keywords, the distribution of keywords, and the relations of keywords. At last, some heuristic rules are given to detect the different states of an emergency event.
(2)
We give the definitions of five impact factors including the number of increased web pages, the number of increased keywords, the number of communities, the average clustering coefficient, and the average similarities of web pages. These five impact factors contain statistic and content information of an event.
(3)
Experiments on real datasets (real web events) show the good performance of the proposed algorithm and verify its effectiveness and robustness. The proposed algorithm can help the social group or government process the emergency events and let the people know an emergency event clearly.The rest of the paper is organized as follows. In Section2, we give the related work of event detection. In Section 3, we formally define the problem and a series of definitions are given. The methods for generating five impact factors are given in Section 4. We discuss our experiments and results in Section 5. At last, some conclusions are given.


## 2. Related Work

The proposed states detection problem is similar to the research of Topic Detection and Tracking (TDT). Various methods have been proposed to manage news stories, spot news events, and track the process of events [17–24]. Usually, the TDT research generates a hierarchical structure of an event, which aims at clustering related news into it. Overall, TDT technologies have been attempting to detect or cluster news stories into these events, without focusing on or interpreting with the sudden, urgent, and unexpected features of emergency events [25]. Since event evolution technologies are similar to the emergency event states detection, we will list some related works about it. Event evolution proposed by Allan [26] is a subtopic of topic detection and tracking. In his study, two important conclusions are given: (1) a seminal event may lead to several other events; (2) the events at the beginning may have more influence on the events coming immediately after than the events at the later time. Allan used the ontology to measure the similarity of events. However, the ontology is difficult to get, which makes the work difficult to be used directly. Mei and Zhai [27] investigated theme evolution which is similar to event evolution. They proposed a temporal pattern discovery technique on the basis of the timestamps of text streams. The theme of each interval is identified, and the evolution of theme between successive intervals is extracted. Unfortunately, the proposed technique did not consider the different states of an event, which may impact its result. Wei and Chang [28] proposed an event evolution pattern discovery technique which identifies event episodes together with their temporal relationships. An event episode is defined as a stage or subevent of an event. The above study differs from this paper: their study deals with an event and their event episodes, whereas this paper handles the different states of emergency events imaged on the web. Later, Yang and Shi [29] aimed at discovering event evolution graphs from news corpora. The proposed event evolution graph is used to present the underlying structure of the events. The proposed method uses the event timestamp, event content similarity, temporal proximity, and web pages distribution proximity to model the event evolution relationships. Recently, Jo et al. [30] studied the method to discover the evolution of topics (i.e., events) over time in a timestamp document collection. They tried to capture the topology of topic evolution that is inherent in a given corpus. They claimed that the topology of the topic evolution discovered by his method is very rich and carries concrete information on how the corpus has evolved over time. Event detection based on prior user queries is reported in [31, 32]. Fung et al. [31] proposed to first identify the bursty features related to the user query and then organize the documents related to those bursty features into an event hierarchy. In [32], a user specifies an event (or a topic) of interest using several keywords as a query. The response to the query is a combination of streams (e.g., news feeds, emails) that are sufficiently correlated and collectively contain all query keywords within a time period. The proposed work is also related to event detection using click-through data [33]. Event ranking with user attention is reported in [34] where the events are firstly detected from news streams. User attention is then derived from the number of page-views (collected through web browser toolbars) for all the news articles in the same event. Leskovec et al. [35, 36] proposed the method for outbreak detection based on cost-effective function.Overall, the above methods have been proved to make good performance on general events other than emergency events. The emergency events possess dynamic, real-time, multistates, sudden, and urgent features. In this paper, we consider the burst feature of an emergency event imaged on the web.


## 3. Problems Formulation

In this section, the basic definition of the proposed method is introduced. The temporal features of an emergency event are given in the next section. The burst factors of the proposed method are given in the last section.


### 3.1. Basic Definitions

An event is something that happens at some specific time and often some specific places [37–39]. In fact, this definition of events from TDT can be relaxed since some events do not happen at some specific place. Many events are launched by some news or stories only on the web which cannot get the exact location stamp. Instead, the time of an emergency event can always be identified since some news of it has an exact timestamp t. Besides the timestamp, in this paper, we only take web pages into consideration since they can be easily processed and analyzed. An emergency event is defined as follows.Definition 1 (emergency event,e).
An emergency evente is a tuple L
e
,
F
e, where L
e is the life course of e, F
e is the set of basic features describing e.Definition 2 (the basic features and life cycle of emergency event imaged on the web).
F
e and L
e. The basic features of an emergency event contain three components including seeds set S
(
t
i
,
t
j
), web pages set φ
(
t
i
,
t
j
), and keywords set ψ
(
t
i
,
t
j
). The life cycle of an emergency event contains the starting and ending timestamps t
s
,
t
e.Seeds set consists of the core keywords of an emergency event from timestampt
i to t
j. Usually, these keywords can be used to search the related web pages covering one web event. For example, we can use “China rail crash” as the seeds to search related web pages covering the event. The seeds set of an emergency event can be found from news website, which provides the hot news topics each day. Besides the seeds set, how to get the web pages related to the emergency event is another issue. Web page set is a set with n related web pages return by search engines using the seeds from timestamp t
i to t
j, which is denoted by φ
(
t
i
,
t
j
)
=
d
1
,
d
2
,
…
,
d
i
,
…
,
d
n. Keywords set is a set with m keywords extracted from φ
(
t
i
,
t
j
), which is denoted by ψ
(
t
i
,
t
j
)
=
k
1
,
k
2
,
…
,
k
i
,
…
,
k
m. Web page d
i is represented by a keyword vector, which is denoted as(1)
d
i
=
w
1
,
w
2
,
…
,
w
m
,where w
j
=
(
1
+
l
o
g
t
f
(
k
j
)
)
∗
l
o
g
(
1
+
n
/
d
f
(
k
j
)
) [38]; t
f
(
k
j
) means the term frequency of keyword k
j in web page d
i; and d
f
(
k
j
) means the web page frequency of keyword k
j in φ
(
t
i
,
t
j
).Herein, we use search engine such as Google (http://www.google.com/) and Baidu (http://www.baidu.com/) to get the web pages related to an emergency event imaged on the web. The reasons are as follows.(1) Updating Information Rapidly. The information of an event refreshes quickly. For example, the information of “Japan nuclear crisis” from social sensors may update per hour and even per minute. Web search engines such as Google provide the interface to search information up to per minute.(2) Different Information Sources. The information of an emergency event usually comes from different sources such as news, blogs, and BBS. Web search engines such as Google and Baidu provide the interface to search information from various websites.


### 3.2. Basic Temporal Features

In this section, we present five basic temporal features including (1) the number of increased web pages, (2) the number of increased keywords, (3) the distribution of keywords on web pages, (4) the associated relations of keywords, and (5) the similarities of web pages.Temporal Feature 1 (the number of increased web pages from timestamp
t
i
to
t
j
,
φ
(
t
i
,
t
j
)
). The elements in φ
(
t
i
,
t
j
) do not appear from the starting timestamp t
s to t
i; that is, ∀
d
n
∈
φ
(
t
i
,
t
j
)
→
d
n
∉
φ
(
t
s
,
t
i
).Temporal Feature 2 (the number of increased keywords from timestamp
t
i
to
t
j
,
ψ
(
t
i
,
t
j
)
). The elements in ψ
(
t
i
,
t
j
) do not appear from the starting timestamp t
s to t
i; that is, ∀
k
m
∈
ψ
(
t
i
,
t
j
)
→
k
m
∉
ψ
(
t
i
,
t
j
).Temporal Feature 3. The distribution of keywords on web pages from timestamp t
i to t
j, ζ
(
t
i
,
t
j
). For an emergency event e, the web pages in φ
(
t
i
,
t
j
) can be represented as a vector by the keywords in ψ
(
t
i
,
t
j
). These vectors can be stored as a matrix: (2)
ζ
t
i
,
t
j
=
w
11
…
w
1
m
⋮
⋱
⋮
w
n
1
⋯
w
n
m
.Temporal Feature 4 (the associated relations of keywords from timestamp
t
i
to
t
j
,
Γ
(
t
i
,
t
j
)
). For an emergency event e, the associated relations of keywords can be stored as a matrix: (3)
Γ
t
i
,
t
j
=
f
11
…
f
1
m
⋮
⋱
⋮
f
m
1
⋯
f
m
m
,where f
i
j means the weight of relation between k
i and k
j, which can be computed by(4)
f
i
j
=
log
⁡
N
k
i
∧
k
j
∗
n
/
N
k
i
∗
N
k
j
log
⁡
n
,where N
(
k
i
) means the number of in φ
(
t
i
,
t
j
) containing k
i and N
(
k
i
∧
k
j
) is the number of web pages in φ
(
t
i
,
t
j
) containing both k
i and k
j.Temporal Feature 5 (the similarities between web pages from timestamp
t
i
to
t
j
,
Ξ
(
t
i
,
t
j
)
). For an emergency event e, the similarities between web pages can be stored as a matrix: (5)
Ξ
t
i
,
t
j
=
a
11
…
a
1
n
⋮
⋱
⋮
a
n
1
⋯
a
n
n
,where a
i
j means the similarities between d
i and d
j, which can be computed by(6)
a
i
j
=
d
i
·
d
j
d
i
d
j
,where d
i and d
j denote the mathematic model of vectors d
i and d
j.


### 3.3. Basic Burst Factors

In this section, we present basic burst factors including the number of communities in context graph, the average clustering coefficient of the context graph, and the average similarities of web pages.Impact Factor 1 (the number of communities in context graph from timestamp
t
i
to
t
j
,
C
(
t
i
,
t
j
)
). A community is a subgraph of the context graph, which reflects a part of context of an event e. The set of communities is a segmentation of the context graph. Each context community is a part of the context graph, which is with no common keywords of other community. The set of communities of an event e is denoted as(7)
C
e
=
c
1
,
c
2
,
…
,
c
C
e
∀
k
i
∈
c
i
∧
k
j
∈
c
j
⟶
k
i
≠
k
j
.Impact Factor 2 (the average clustering coefficient [24] of the context graph from timestamp
t
i
to
t
j
,
C
C
(
t
i
,
t
j
)
). In graph theory, a clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. The clustering coefficient of the keyword k
i in context graph can be computed by(8)
C
C
k
i
=
2
l
p
p
-
1
,where p means the number of neighbor node of the keyword k
i and l means the number of edges between these neighbor nodes. Thus, the average clustering coefficient of the context graph can be computed by (9)
C
C
t
i
,
t
j
=
∑
i
=
1
m
C
C
k
i
m
.Impact Factor 3 (the average similarities of web pages from timestamp
t
i
to
t
j
,
A
S
(
t
i
,
t
j
)
). For an event e, the similarities can be computed by cosine function:(10)
Sim
d
i
,
d
j
=
d
i
·
d
j
d
i
d
j
,where d
i and d
j denote the mathematic model of vectors d
i and d
j. Thus, the average similarities of web pages can be computed by(11)
A
S
t
i
,
t
j
=
∑
i
=
1
m
∑
j
=
1
m
S
i
m
d
i
,
d
j
m
m
-
1
.


## 3.1. Basic Definitions

An event is something that happens at some specific time and often some specific places [37–39]. In fact, this definition of events from TDT can be relaxed since some events do not happen at some specific place. Many events are launched by some news or stories only on the web which cannot get the exact location stamp. Instead, the time of an emergency event can always be identified since some news of it has an exact timestamp t. Besides the timestamp, in this paper, we only take web pages into consideration since they can be easily processed and analyzed. An emergency event is defined as follows.Definition 1 (emergency event,e).
An emergency evente is a tuple L
e
,
F
e, where L
e is the life course of e, F
e is the set of basic features describing e.Definition 2 (the basic features and life cycle of emergency event imaged on the web).
F
e and L
e. The basic features of an emergency event contain three components including seeds set S
(
t
i
,
t
j
), web pages set φ
(
t
i
,
t
j
), and keywords set ψ
(
t
i
,
t
j
). The life cycle of an emergency event contains the starting and ending timestamps t
s
,
t
e.Seeds set consists of the core keywords of an emergency event from timestampt
i to t
j. Usually, these keywords can be used to search the related web pages covering one web event. For example, we can use “China rail crash” as the seeds to search related web pages covering the event. The seeds set of an emergency event can be found from news website, which provides the hot news topics each day. Besides the seeds set, how to get the web pages related to the emergency event is another issue. Web page set is a set with n related web pages return by search engines using the seeds from timestamp t
i to t
j, which is denoted by φ
(
t
i
,
t
j
)
=
d
1
,
d
2
,
…
,
d
i
,
…
,
d
n. Keywords set is a set with m keywords extracted from φ
(
t
i
,
t
j
), which is denoted by ψ
(
t
i
,
t
j
)
=
k
1
,
k
2
,
…
,
k
i
,
…
,
k
m. Web page d
i is represented by a keyword vector, which is denoted as(1)
d
i
=
w
1
,
w
2
,
…
,
w
m
,where w
j
=
(
1
+
l
o
g
t
f
(
k
j
)
)
∗
l
o
g
(
1
+
n
/
d
f
(
k
j
)
) [38]; t
f
(
k
j
) means the term frequency of keyword k
j in web page d
i; and d
f
(
k
j
) means the web page frequency of keyword k
j in φ
(
t
i
,
t
j
).Herein, we use search engine such as Google (http://www.google.com/) and Baidu (http://www.baidu.com/) to get the web pages related to an emergency event imaged on the web. The reasons are as follows.(1) Updating Information Rapidly. The information of an event refreshes quickly. For example, the information of “Japan nuclear crisis” from social sensors may update per hour and even per minute. Web search engines such as Google provide the interface to search information up to per minute.(2) Different Information Sources. The information of an emergency event usually comes from different sources such as news, blogs, and BBS. Web search engines such as Google and Baidu provide the interface to search information from various websites.


## 3.2. Basic Temporal Features

In this section, we present five basic temporal features including (1) the number of increased web pages, (2) the number of increased keywords, (3) the distribution of keywords on web pages, (4) the associated relations of keywords, and (5) the similarities of web pages.Temporal Feature 1 (the number of increased web pages from timestamp
t
i
to
t
j
,
φ
(
t
i
,
t
j
)
). The elements in φ
(
t
i
,
t
j
) do not appear from the starting timestamp t
s to t
i; that is, ∀
d
n
∈
φ
(
t
i
,
t
j
)
→
d
n
∉
φ
(
t
s
,
t
i
).Temporal Feature 2 (the number of increased keywords from timestamp
t
i
to
t
j
,
ψ
(
t
i
,
t
j
)
). The elements in ψ
(
t
i
,
t
j
) do not appear from the starting timestamp t
s to t
i; that is, ∀
k
m
∈
ψ
(
t
i
,
t
j
)
→
k
m
∉
ψ
(
t
i
,
t
j
).Temporal Feature 3. The distribution of keywords on web pages from timestamp t
i to t
j, ζ
(
t
i
,
t
j
). For an emergency event e, the web pages in φ
(
t
i
,
t
j
) can be represented as a vector by the keywords in ψ
(
t
i
,
t
j
). These vectors can be stored as a matrix: (2)
ζ
t
i
,
t
j
=
w
11
…
w
1
m
⋮
⋱
⋮
w
n
1
⋯
w
n
m
.Temporal Feature 4 (the associated relations of keywords from timestamp
t
i
to
t
j
,
Γ
(
t
i
,
t
j
)
). For an emergency event e, the associated relations of keywords can be stored as a matrix: (3)
Γ
t
i
,
t
j
=
f
11
…
f
1
m
⋮
⋱
⋮
f
m
1
⋯
f
m
m
,where f
i
j means the weight of relation between k
i and k
j, which can be computed by(4)
f
i
j
=
log
⁡
N
k
i
∧
k
j
∗
n
/
N
k
i
∗
N
k
j
log
⁡
n
,where N
(
k
i
) means the number of in φ
(
t
i
,
t
j
) containing k
i and N
(
k
i
∧
k
j
) is the number of web pages in φ
(
t
i
,
t
j
) containing both k
i and k
j.Temporal Feature 5 (the similarities between web pages from timestamp
t
i
to
t
j
,
Ξ
(
t
i
,
t
j
)
). For an emergency event e, the similarities between web pages can be stored as a matrix: (5)
Ξ
t
i
,
t
j
=
a
11
…
a
1
n
⋮
⋱
⋮
a
n
1
⋯
a
n
n
,where a
i
j means the similarities between d
i and d
j, which can be computed by(6)
a
i
j
=
d
i
·
d
j
d
i
d
j
,where d
i and d
j denote the mathematic model of vectors d
i and d
j.


## 3.3. Basic Burst Factors

In this section, we present basic burst factors including the number of communities in context graph, the average clustering coefficient of the context graph, and the average similarities of web pages.Impact Factor 1 (the number of communities in context graph from timestamp
t
i
to
t
j
,
C
(
t
i
,
t
j
)
). A community is a subgraph of the context graph, which reflects a part of context of an event e. The set of communities is a segmentation of the context graph. Each context community is a part of the context graph, which is with no common keywords of other community. The set of communities of an event e is denoted as(7)
C
e
=
c
1
,
c
2
,
…
,
c
C
e
∀
k
i
∈
c
i
∧
k
j
∈
c
j
⟶
k
i
≠
k
j
.Impact Factor 2 (the average clustering coefficient [24] of the context graph from timestamp
t
i
to
t
j
,
C
C
(
t
i
,
t
j
)
). In graph theory, a clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. The clustering coefficient of the keyword k
i in context graph can be computed by(8)
C
C
k
i
=
2
l
p
p
-
1
,where p means the number of neighbor node of the keyword k
i and l means the number of edges between these neighbor nodes. Thus, the average clustering coefficient of the context graph can be computed by (9)
C
C
t
i
,
t
j
=
∑
i
=
1
m
C
C
k
i
m
.Impact Factor 3 (the average similarities of web pages from timestamp
t
i
to
t
j
,
A
S
(
t
i
,
t
j
)
). For an event e, the similarities can be computed by cosine function:(10)
Sim
d
i
,
d
j
=
d
i
·
d
j
d
i
d
j
,where d
i and d
j denote the mathematic model of vectors d
i and d
j. Thus, the average similarities of web pages can be computed by(11)
A
S
t
i
,
t
j
=
∑
i
=
1
m
∑
j
=
1
m
S
i
m
d
i
,
d
j
m
m
-
1
.


## 4. Computing the Burst Power

In this section, based on the above definitions, the method for computing the burst power of an emergency event is proposed.


### 4.1. Basic Definitions of Burst Power

After giving the basic temporal features of emergency events, we define burst power as follows.Definition 3 (burst power).
o
p
(
t
i
,
t
j
). For an emergency event e, the burst power from timestamp t
i to t
j is the influence degree on the society.For example, highφ
(
t
i
,
t
j
) or ψ
(
t
i
,
t
j
) means high influence degree of an event on the society; thus the event has high burst power.According to the characteristic of burst power, the time interval with high influence to the society will possess high possibility to be the peak or milestone of an emergency event. Inspired by [40], before we propose the algorithm to compute the burst power, we introduce two important definitions as follows.Definition 4 (the representative power of keywords).
r
p
(
k
). The representative power of keyword k is the probability of k to represent the event e correctly.Definition 5 (the confidence of web pages).
c
w
(
d
). The confidence of a web page d is the expected representative power of keywords provided by d.Different keywords related to one event reveal the various aspects of the event. For example, the keyword “China” reveals the place of the event “China rail crash.” On the other hand, the keywords “rail” and “crash” reveal the object of the event “China rail crash.”


### 4.2. Basic Heuristics for Computing Burst Power

Based on the common sense and the observations on real data, we have four basic heuristic rules which serve as the bases for the computing of burst power. These four heuristic rules are relevant to the data. If there is burst situation in the data, they would be correct. Given the discussion field of this paper, all emergency events have some different effect and spreading power. Thus, these four heuristic rules are appropriate for emergency events situation.Heuristic Rule 1. If ignoring ψ
(
t
i
,
t
j
) and ζ
(
t
i
,
t
j
), the possibility of time interval (
t
i
,
t
j
) with high burst power is increasing with φ
(
t
i
,
t
j
).According to heuristic rule 1, the burst power is proportional to the number of increased web pages. So we can geto
p
(
t
i
,
t
j
)
∞
φ
(
t
i
,
t
j
).Heuristic Rule 2. If ignoring φ
(
t
i
,
t
j
) and ζ
(
t
i
,
t
j
), the possibility of time interval (
t
i
,
t
j
) with high burst power is increasing with ψ
(
t
i
,
t
j
).According to heuristic rule 2, the burst power is proportional to the number of increased keywords. So we can geto
p
(
t
i
,
t
j
)
∞
ψ
(
t
i
,
t
j
).If two time intervals with the sameφ
(
t
i
,
t
j
) and ψ
(
t
i
,
t
j
), the distribution of keywords will determine o
p
(
t
i
,
t
j
). So, we give heuristic rule 3.Heuristic Rule 3. If the bipartite graph of ζ
(
t
i
,
t
j
) is a complete graph, o
p
(
t
i
,
t
j
) is the lowest; that is, (
∀
w
n
m
∈
ζ
(
t
i
,
t
j
)
→
w
n
m
≠
0
)
→
o
p
(
t
i
,
t
j
)
m
i
n.According to heuristic rule 3, if all of the keywords appear in each web page, the similarity between them is 1, which means all of the web pages are copies from one web page. This situation means that the emergency event is with the lowest diversity.Sinceψ
(
t
i
,
t
j
) and φ
(
t
i
,
t
j
) are dependent, the distribution of keywords on the web pages should be considered. So, we give heuristic rule 4.Heuristic Rule 4. Since ψ
(
t
i
,
t
j
) and φ
(
t
i
,
t
j
) are dependent, the distribution of keywords on web pages should be considered. If all of the keywords are provided by only one web page, o
p
(
t
i
,
t
j
) is the highest.


### 4.3. Computing the Burst Power

Heuristic rule 4 gives the condition of maximumo
p
(
t
i
,
t
j
). Figure 1 gives the illustration of heuristic rules 3 and 4. Based on heuristic rules 3 and 4, we can conclude that the confidence of a web page and the representative power of a keyword are determined by each other, and we can use an iterative method to compute them. Thus, we compute the confidence of a web page by calculating the average representative power of keywords it provides as follows:(12)
c
w
d
h
=
∑
k
m
∈
d
h
⃑
∩
w
h
n
>
0
r
p
k
m
d
h
⃑
,where d
h
⃑ means the number of web pages with keywords k
m.Figure 1
The illustration of the maximum and minimum burst power.Inspired by [40], we use probability function to compute the representative power of keywords:(13)
r
p
k
m
=
1
-
∏
d
h
∈
k
m
⃑
∩
w
h
m
>
0
1
-
c
w
d
h
,where k
m
⃑ is the set of web pages providing k
m.The above two equations show how to compute the confidence of a web page. However, since the similarities between web pages are not zero, we put the similarities between web pages into (8). The equation can be revised as (9), which considers the similarities between web pages:(14)
r
p
′
k
m
=
r
p
k
m
+
∑
k
i
∈
k
k
i
⃑
∩
f
i
j
>
0
f
i
j
∗
r
p
k
i
,where k
k
i
⃑ is the set of keywords similarities against keyword k
i.Sincer
p
′
(
k
) may be higher than 1, we adopt the widely used logistic function to set r
p
′
(
k
) into (
0
,
1
). Then (9) can be revised as(15)
r
p
′
′
k
m
=
1
1
+
e
-
r
p
′
k
m
.Equation (7) is revised as(16)
c
w
d
h
=
∑
k
m
∈
d
h
⃑
∩
w
h
m
>
0
r
p
′
′
k
m
d
h
⃑and the burst power function of time interval (
t
i
,
t
j
) can be computed by the sum of confidence of all web pages:(17)
o
p
t
i
,
t
j
=
∑
h
=
1
n
1
-
c
w
d
h
,where n means the number of web pages from time interval (
t
i
,
t
j
).As described above, we can compute the burst power of the proposed method.


## 4.1. Basic Definitions of Burst Power

After giving the basic temporal features of emergency events, we define burst power as follows.Definition 3 (burst power).
o
p
(
t
i
,
t
j
). For an emergency event e, the burst power from timestamp t
i to t
j is the influence degree on the society.For example, highφ
(
t
i
,
t
j
) or ψ
(
t
i
,
t
j
) means high influence degree of an event on the society; thus the event has high burst power.According to the characteristic of burst power, the time interval with high influence to the society will possess high possibility to be the peak or milestone of an emergency event. Inspired by [40], before we propose the algorithm to compute the burst power, we introduce two important definitions as follows.Definition 4 (the representative power of keywords).
r
p
(
k
). The representative power of keyword k is the probability of k to represent the event e correctly.Definition 5 (the confidence of web pages).
c
w
(
d
). The confidence of a web page d is the expected representative power of keywords provided by d.Different keywords related to one event reveal the various aspects of the event. For example, the keyword “China” reveals the place of the event “China rail crash.” On the other hand, the keywords “rail” and “crash” reveal the object of the event “China rail crash.”


## 4.2. Basic Heuristics for Computing Burst Power

Based on the common sense and the observations on real data, we have four basic heuristic rules which serve as the bases for the computing of burst power. These four heuristic rules are relevant to the data. If there is burst situation in the data, they would be correct. Given the discussion field of this paper, all emergency events have some different effect and spreading power. Thus, these four heuristic rules are appropriate for emergency events situation.Heuristic Rule 1. If ignoring ψ
(
t
i
,
t
j
) and ζ
(
t
i
,
t
j
), the possibility of time interval (
t
i
,
t
j
) with high burst power is increasing with φ
(
t
i
,
t
j
).According to heuristic rule 1, the burst power is proportional to the number of increased web pages. So we can geto
p
(
t
i
,
t
j
)
∞
φ
(
t
i
,
t
j
).Heuristic Rule 2. If ignoring φ
(
t
i
,
t
j
) and ζ
(
t
i
,
t
j
), the possibility of time interval (
t
i
,
t
j
) with high burst power is increasing with ψ
(
t
i
,
t
j
).According to heuristic rule 2, the burst power is proportional to the number of increased keywords. So we can geto
p
(
t
i
,
t
j
)
∞
ψ
(
t
i
,
t
j
).If two time intervals with the sameφ
(
t
i
,
t
j
) and ψ
(
t
i
,
t
j
), the distribution of keywords will determine o
p
(
t
i
,
t
j
). So, we give heuristic rule 3.Heuristic Rule 3. If the bipartite graph of ζ
(
t
i
,
t
j
) is a complete graph, o
p
(
t
i
,
t
j
) is the lowest; that is, (
∀
w
n
m
∈
ζ
(
t
i
,
t
j
)
→
w
n
m
≠
0
)
→
o
p
(
t
i
,
t
j
)
m
i
n.According to heuristic rule 3, if all of the keywords appear in each web page, the similarity between them is 1, which means all of the web pages are copies from one web page. This situation means that the emergency event is with the lowest diversity.Sinceψ
(
t
i
,
t
j
) and φ
(
t
i
,
t
j
) are dependent, the distribution of keywords on the web pages should be considered. So, we give heuristic rule 4.Heuristic Rule 4. Since ψ
(
t
i
,
t
j
) and φ
(
t
i
,
t
j
) are dependent, the distribution of keywords on web pages should be considered. If all of the keywords are provided by only one web page, o
p
(
t
i
,
t
j
) is the highest.


## 4.3. Computing the Burst Power

Heuristic rule 4 gives the condition of maximumo
p
(
t
i
,
t
j
). Figure 1 gives the illustration of heuristic rules 3 and 4. Based on heuristic rules 3 and 4, we can conclude that the confidence of a web page and the representative power of a keyword are determined by each other, and we can use an iterative method to compute them. Thus, we compute the confidence of a web page by calculating the average representative power of keywords it provides as follows:(12)
c
w
d
h
=
∑
k
m
∈
d
h
⃑
∩
w
h
n
>
0
r
p
k
m
d
h
⃑
,where d
h
⃑ means the number of web pages with keywords k
m.Figure 1
The illustration of the maximum and minimum burst power.Inspired by [40], we use probability function to compute the representative power of keywords:(13)
r
p
k
m
=
1
-
∏
d
h
∈
k
m
⃑
∩
w
h
m
>
0
1
-
c
w
d
h
,where k
m
⃑ is the set of web pages providing k
m.The above two equations show how to compute the confidence of a web page. However, since the similarities between web pages are not zero, we put the similarities between web pages into (8). The equation can be revised as (9), which considers the similarities between web pages:(14)
r
p
′
k
m
=
r
p
k
m
+
∑
k
i
∈
k
k
i
⃑
∩
f
i
j
>
0
f
i
j
∗
r
p
k
i
,where k
k
i
⃑ is the set of keywords similarities against keyword k
i.Sincer
p
′
(
k
) may be higher than 1, we adopt the widely used logistic function to set r
p
′
(
k
) into (
0
,
1
). Then (9) can be revised as(15)
r
p
′
′
k
m
=
1
1
+
e
-
r
p
′
k
m
.Equation (7) is revised as(16)
c
w
d
h
=
∑
k
m
∈
d
h
⃑
∩
w
h
m
>
0
r
p
′
′
k
m
d
h
⃑and the burst power function of time interval (
t
i
,
t
j
) can be computed by the sum of confidence of all web pages:(17)
o
p
t
i
,
t
j
=
∑
h
=
1
n
1
-
c
w
d
h
,where n means the number of web pages from time interval (
t
i
,
t
j
).As described above, we can compute the burst power of the proposed method.


## 5. Experiments and Analysis

### 5.1. Datasets

The events in our experiments are extracted from Google and Baidu. We select 150 events with about 1,500,000 web pages in our experiments including politics events, accidents events, disasters events, and terrorism events. The web pages of each event are downloaded from Google. Stanford tagger (http://nlp.stanford.edu/) is used to reserve the noun words in the web pages. The keywords are selected by their document frequencies. Table 1 shows the statistics of our experimental dataset. When Google and Baidu provide the events, it also gives some keywords for helping users to search them. After we get the seed set of an event by the search engine, a certain number of the web pages are collected as samples by automatic crawling and searching with the seed set. The detailed steps for collecting related web resources of an event in our experiments are as follows.(1)
Get the seed set of an event such as “China train crash,” which can be seen asS
(
t
i
,
t
j
) of an event.
(2)
Search the seed set as the query and download the related web pages with search engine, which can be seen asφ
(
t
i
,
t
j
) of an event.
(3)
Identify the starting timestamp of an event byφ
(
t
i
,
t
j
) and the ending timestamp by download time, which can be seen as t
s and t
e of an event.
(4)
Getφ
(
t
i
,
t
j
), ψ
(
t
i
,
t
j
), ζ
(
t
i
,
t
j
), and Ξ
(
t
i
,
t
j
) per day.
(5)
Do step(
4
) of different information sources including news, blogs, and BBS.Table 1
The details of datasets.
Feature
Value
Average number of seeds per event
2
Average number of web pages per event
1012
Average number of keywords per event
4534
Average number of days per event
30
Average number of web pages per day
34
Average number of keywords per day
853


### 5.2. Experimental Results

After obtaining the temporal features per day of each event, we select ten human annotators to test whether the burst power of each event is correct or not. The data from Google Trends is selected to compare with that of the proposed method. If the human annotator thinks the proposed methods are equal to his own imagination or Google Trends, we set the precision of this detection to true. In additional, the annotators are set to do their evaluations independently, which ensure the reliability and validity of the results. Before the human annotator started to evaluate the experimental results, we provide the abstract descriptions of each event for them. For example, we will give some news stories and concepts to the human annotators. This training session continued until the human annotators are familiar with the concepts and the temporal feature of events. In the next step, each annotator was asked to test the results of each event independently.In fact, the overall precision of the proposed method achieves 92%, showing the accuracy of our burst power computation algorithm. From the experiments on the real data we know that the proposed algorithm can compute the burst power of an event accurately. The information from web can be integrated into burst power. The factor can be used to detect states of an emergency event.


## 5.1. Datasets

The events in our experiments are extracted from Google and Baidu. We select 150 events with about 1,500,000 web pages in our experiments including politics events, accidents events, disasters events, and terrorism events. The web pages of each event are downloaded from Google. Stanford tagger (http://nlp.stanford.edu/) is used to reserve the noun words in the web pages. The keywords are selected by their document frequencies. Table 1 shows the statistics of our experimental dataset. When Google and Baidu provide the events, it also gives some keywords for helping users to search them. After we get the seed set of an event by the search engine, a certain number of the web pages are collected as samples by automatic crawling and searching with the seed set. The detailed steps for collecting related web resources of an event in our experiments are as follows.(1)
Get the seed set of an event such as “China train crash,” which can be seen asS
(
t
i
,
t
j
) of an event.
(2)
Search the seed set as the query and download the related web pages with search engine, which can be seen asφ
(
t
i
,
t
j
) of an event.
(3)
Identify the starting timestamp of an event byφ
(
t
i
,
t
j
) and the ending timestamp by download time, which can be seen as t
s and t
e of an event.
(4)
Getφ
(
t
i
,
t
j
), ψ
(
t
i
,
t
j
), ζ
(
t
i
,
t
j
), and Ξ
(
t
i
,
t
j
) per day.
(5)
Do step(
4
) of different information sources including news, blogs, and BBS.Table 1
The details of datasets.
Feature
Value
Average number of seeds per event
2
Average number of web pages per event
1012
Average number of keywords per event
4534
Average number of days per event
30
Average number of web pages per day
34
Average number of keywords per day
853


## 5.2. Experimental Results

After obtaining the temporal features per day of each event, we select ten human annotators to test whether the burst power of each event is correct or not. The data from Google Trends is selected to compare with that of the proposed method. If the human annotator thinks the proposed methods are equal to his own imagination or Google Trends, we set the precision of this detection to true. In additional, the annotators are set to do their evaluations independently, which ensure the reliability and validity of the results. Before the human annotator started to evaluate the experimental results, we provide the abstract descriptions of each event for them. For example, we will give some news stories and concepts to the human annotators. This training session continued until the human annotators are familiar with the concepts and the temporal feature of events. In the next step, each annotator was asked to test the results of each event independently.In fact, the overall precision of the proposed method achieves 92%, showing the accuracy of our burst power computation algorithm. From the experiments on the real data we know that the proposed algorithm can compute the burst power of an event accurately. The information from web can be integrated into burst power. The factor can be used to detect states of an emergency event.


## 6. Conclusions

With the popularity of web, the internet is becoming a major information provider and poster of an event due to its real-time, open, and dynamic features. However, faced with the hugeness, disorder, and continuous web resources, it is impossible for people to efficiently recognize, collect, and organize the events. In this paper, crowd sensing based burst computation algorithm of a web event is developed in order to let the people know a web event clearly and help the social group or government process the events effectively. The definition of “social sensors” is firstly introduced, which is the foundation of using web resources to compute the burst power of events on the web. Secondly, different temporal features of web events are developed to provide the basics for the proposed computation algorithm. Moreover, the burst power is presented to integrate the above temporal features of an event. Empirical experiments on real datasets including Google Zeitgeist and Google Trends show that that the number of web pages and the average clustering coefficient can be used to detect events. Some strategies integrating the number of web pages and the average clustering coefficient are also employed. The evaluations on real dataset show that the proposed function integrating the number of web pages and the average clustering coefficient can be used for event detection efficiently and correctly.



---

*Source: 184751-2015-05-31.xml*