NetMob 2010
Workshop on the
Analysis of Mobile Phone Networks
MIT, Cambridge, USA
May 11, 2010

Program and Book of Abstracts
Edited by: Vincent Blondel and Gautier Krings

Organizing Committee:
Chair: Vincent Blondel
Francesco Calabrese
Gautier Krings
Benjamin Waber

UCLouvain (Belgium)
Senseable City Lab, MIT
UCLouvain (Belgium)
Media Lab, MIT
Book of abstracts for NetMob 20101

Book of abstracts for NetMob 2010

2

Scientific Committee:
Chair: Vincent Blondel
Laszlo Barabási
Rob Claxton
Vittoria Colizza
Massimo Colonna
Nathan Eagle
Alexandre GerberMarta Gonzales
Cesar Hidalgo
János Kertész
Renaud LambiotteDavid Lazer
Jure Leskovec
Nuria Oliver
Jukka-Pekka Onnela
Asu Ozdaglar
Alex (Sandy) Pentland
Mason Porter
Carlo Ratti
Jari Saramäki
Leonardo Soto
Zbigniew Smoreda
John Tsitsiklis
Paul Van Dooren

UCLouvain (Belgium)
Northeastern University
British Telecom (UK)ISI Foundation (Italy)
Telecom Italia (Italy)
Santa Fe Institute
AT&T Research
MIT
Harvard University
Budapest University of Technology (Hungary)
Imperial College (UK)
Northeastern University
Stanford University
Telefonica Research (Spain)
Harvard University
LIDS, MITMedia Lab, MIT
University of Oxford (UK)
Senseable City Lab, MIT
Helsinki University of Technology (Finland)
AirSageOrange Labs (France)
LIDS, MITUCLouvain (Belgium)Book of abstracts for NetMob 20103

Book of abstracts for NetMob 2010

4

NetMob 2010
Workshop on the

Analysis of Mobile Phone Networks

PROGRAM

8:45-9:15 Registration

Session A (9:15-10:45)
9:15-9:30
Workshop overview: trends in mobile phone network
analysisVincent Blondel, UCLouvain
9:30-9:45
Age, Gender and Communication Networks
A. Stoica (1,2), Z. Smoreda (1), C. Prieur (2), J.-L. Guillaume (3)(1) SENSe/Orange Labs
(2) LIAFA/Université Paris 7(3) LIP6/Université Paris 6
p.11
9:45-10:00 Geography of Social Groups
S. Arbesman, J.-P. Onnela, N.A. Christakis
Harvard Medical School
p.15
10:00-10:15 From Wireless Contacts to Community Structures
T. Hossmann, T. Spyropoulos, F. Legendre
Computer Engineering and Networks Laboratory, ETH Zurich
p.16
10:15-10:30 Social Relationship and Behavior Analysis in Mobile Social
Networks
H. Zhang, R. Dantu
Dept. of Computer Science and Engineering, University of North Texas
p.19
10:30-11:00 Coffee breakBook of abstracts for NetMob 20105

Session B (11:00-12:15)
11:00-11:15 Timescales in evolving mobile networks
G.M. Krings (1), M. Karsai (2), J. Saramäki (2), V.D. Blondel (1)(1) UCLouvain(2) BECS, School of Science and Technology, Aalto University
p.27
11:15-11:30 Towards an investigation of the structure and temporal
dynamics in a large scale telecoms dataset
F. Reid, N. Hurley
Clique Research Cluster, University College Dublin
p.28
11:30-11:45 Dynamics and temporal correlations in mobile phone basedsocial networks
M. Karsai (1), L. Kovanen (1), M. Kivelä (1), R. K. Pan (1), J. Saramäki (1), J.
Kertész (2), A.-L. Barabási (3,4), K. Kaski (1)(1) BECS, School of Science and Technology, Aalto University(2) Institute of Physics, Budapest University of Technology and Economics(3) CCNR, Northeastern University(4) CCSB, Dana-Farber Cancer Institutep.32
11:45-12:00 Characterize Mobile Communication Network Using
Communication Motifs
Q. Zhao, N. Oliver
Telefonica Research and Development
p.33
12:00-12:15 Mobility, Data Mining and Privacy: The GeoPKDD Paradigm
F. Giannotti, F. Pinelli, S. Rinzivillo, R. Trasarti
KDD Lab – ISTI – CNR
p.36

12:15-14:00 Lunch breakBook of abstracts for NetMob 2010

6

Session C (14:00-15:45)
14:00-14:15 Epidemics on Mobile Phone Networks
P. Wang (1), M.C. González (2), R. Menezes (3), A.-L. Barabási (1)(1) Center for Complex Network Research, Northeastern University(2) Dept. of Civil and Environmental Engineering, MIT(3) Dept. of Computer Sciences, Florida Institute of Technology
p.43
14:15-14:30 Human movements and the spread of infectious diseases
V. Belik (1), T. Geisel (1), D. Brockmann (2)(1) Max-Planck-Institute for Dynamics and Self-Organization(2) Northwestern University
p.44
14:30-14:45 A Tale of Two Cities
S. Isaacman (1), R. Becker (2), R. Cáceres (2), S. Kobourov (3), J. Rowland(2), A. Varshavsky (2)(1) Dept. of Electrical Engineering, Princeton University(2) AT&T Labs – Research(3) Dept. of Computer Science, University of Arizonap.50
14:45-15:00 Predicting travelling activity space based on phoning
activity space in social networks
D. Janssens, S. Moerdijk
Hasselt University
p.53
15:00-15:15 Preliminary findings on application of mobile phone data
analysis to urban studies
F. Manfredini, P. Pucci, P. Tagliolato, P. Dilda
Dipartimento di Architettura e Pianificazione, Politecnico di Milano
p.56
15:15-15:30 Analyzing cell-phone mobility and social events
F. Calabrese, G. Di Lorenzo, F. Pereira, L. Liu, C. Ratti
Senseable City Laboratory, Massachusetts Institute of Technology
p.59
15:30-15:45 Paris by Night
C. Cariou (1), C. Ziemlicki (2), Z. Smoreda (2)(1) Everydatalab(2) SENSe/Orange Labs
p.62

15:45-16:15 Coffee breakBook of abstracts for NetMob 20107

Session D (16:15-17:00)
16:15-16:30 The “Friends and Family” Mobile Phone Study: Overview
and Initial Report
N. Aharony, C. Ip, W. Pan, A. Pentland
Media Lab, Massachusetts Institute of Technology
p.69
16:30-16:45 Efficient Collaborative Application Monitoring Scheme for
Mobile Networks
Y. Altshuler (1), S. Dolev (2), Y. Elovici (1), N. Aharony (3)(1) Deutsche Telekom Labs, Ben Gurion University(2) Computer Science Dept. Ben Gurion University(3) Media Lab, Massachusetts Institute of Technology
p.72
16:45-17:00 Beyond San Francisco Cabs: building a *-lity Mining
DatasetM.-O. Killijian (1), M. Roy (1), G. Trédan (2)(1) CNRS, LAAS, Université Toulouse(2) TU Berlin
p.75
Concluding Talk
17:00-17:30 Mining Large Scale Cell Phone Data
J. Bolot
Sprintp.79

Book of abstracts for NetMob 20108

Session A

Book of abstracts for NetMob 20109

Book of abstracts for NetMob 201010

NetMob - Analysis of Mobile Phone Networks 2010 – communication proposal

Age, Gender and Communication Networks
Alina Stoicaa,b, Zbigniew Smoredaa, Christophe Prieurb, Jean-Loup Guillaumec
a. SENSe/Orange Labs (alinamihaela.stoica, zbigniew.smoreda@orange-ftgroup.com)
b. LIAFA/Université Paris 7 (prieur@liafa.jussieu.fr)
c. LIP6/Université Paris 6 (jean-loup.guillaume@lip6.fr)
We compared the age and gender distribution of the mobile
phone customers in our dataset to the general national
population and concluded that there is no systematic bias inoperator’s customer as regarding these two characteristics(except for people aged over 60 who are underrepresented
amongst cellular users).

Abstract—In this paper, we address some sociological andtopological issues associated with mobile phone communication.
Based on a dataset of a few million users, we use customers’ age
and gender information to study relation between theseparameters and the average behavior of users in terms of numberof calls, number of SMS and calls duration. We also study thedataset from a networking point of view: we define different
profiles based on the topological properties of the personal
network of each individual and study the relations between these
profiles and the age of customers.

III.

A. Voice–text usages: a generational transformation?
The mobile phone diffusion started in the mid-1990.
Classically, it first touched the young and wealthy part of thedeveloped countries population before the rapid, massive andnearly universal adoption [5]. From the usage point of view, itmeans that nowadays only the youngest groups of the
population were entered in their ―communication age‖ directlywith a cell phone at hand. Hence, it seems interesting to look atsome basic indicators of the mobile phone usages by age.
Figure 1 shows the average number of calls and SMS, and themean call duration by age. We observe that the differences invoice call frequency or duration between ages are relatively
minor. The main distinction concerns SMS usage: younger
users send more SMS than older ones. In the age group 18 to
25 this tendency is really impressive: the SMS is used 4 times
more frequently than a conversational exchange!

Keywords: mobile phone, age, gender, network structure

I.

INTRODUCTION

The ICTs landscape has been entirely changed by the cell
phone diffusion. This individual and ubiquitous device,offering voice and text communication features, hastransformed the frequency and the geography ofcommunication as compared to older fixed phone practices. We
are now virtually always accessible to others wherever we are.
Moreover, the mobile phone gives us a direct access to aperson: the phone line is no more filtered by household’s orbureau’s ―switchboard‖ [4]. This offers a useful insight into
individual behavior and personal and social network analysis.
The recent possibility to analyze large datasets of
behavioral data coming from telecommunication operators
gives us the opportunity to revisit some older research on
telephone usages. It offers also a new prospect to work on
nearly complete interpersonal communication networks.
Among an increasing amount of behavioral traces collected bytechnical systems (internet, mail, IM, SNS…), the interpersonalcommunication data seem to be the best proxy of social
interactions [1,2,3]. Indeed, we usually talk to people with whom
we also have many other links, which is not always true in thecase of communication with email contacts or SNS ―friends‖.
Such datasets therefore open the door to the analysis of closesocial relationship.
II.

RESULTSDATASET

The raw data analyzed in this contribution – the CDRs (Call
Detail Records) – contain all mobile phone exchanges observedin 2006/2007 over a six-month period between Belgiancustomers of a local mobile operator. After data cleaning thedataset contains 3.3 million users that exchanged over 6 billion
calls and short messages (SMS). In addition to communication
details (date, hour, duration of call), this anonymous dataset
also includes customers’ age and gender.

Figure 1. Average monthly number of calls, number of SMS and callduration as a function of phone user's age.

These data show that today interpersonal mobile
communication is clearly distributed between voice and text
exchanges.

1Book of abstracts for NetMob 201011

NetMob - Analysis of Mobile Phone Networks 2010 – communication proposal

601, the probability that an individual of that age belongs to agiven profile (see: figure 2). The range of probabilities isdifferent for different profiles which is due to the overrepresentation of profiles 2 and 6 caused by the heterogeneous
distribution of parameters, with many small values. However,there are important differences between these probabilities fordifferent ages. We observe that middle age people (30 to 45)
are generally involved in sparser structures when younger andolder groups are more densely connected. However, the oldest
keep a densely connected group even if they have isolated
contacts, while the youngest belong to some cliques (profile 4)or have one or more correspondents who are the ―stars‖ of theirego-centered networks (profile 5).

B. Age groups and individual network profiles
To develop these observations, we decided to test whether
there is a relationship between the age of a person and the way
she is linked to others, or not. We thus analyzed theconnections between individuals from the perspective of thecommunication network they belong to.
We represented the interpersonal communications by anundirected simple graph, where the vertices are the mobile
phone customers. Two vertices are connected by an undirectededge if there had been at least one communication in eachdirection between the corresponding users during each monthof the observation. This means that we only consider relatively
strong interpersonal links. This gives us a social network withapproximately 3 million vertices and 7 million edges that we
use in order to characterize customers. Rather than a global
approach, we decided to analyze the local structure of the grapharound each vertex. More precisely we studied the personal (orego-centered) network of each vertex (ego), i.e., the graphwhose vertices are ego's neighbors and whose edges are theedges between the neighbors (note that ego is not included inits ego-centered network).
For every ego we computed several parameters of its egocentered network: the number of vertices (ego's degree), thenumber of edges (the edges between ego's neighbors), thenumber of isolated vertices (the neighbors that are connected
only to ego and not to any other neighbor of ego), the numberof triangles (a group of 3 interconnected neighbors) and thenumber of ―stars‖ (a group of 4 neighbors where one of them isconnected to the other 3 that are unconnected between them).
We use these simple network motives to identify specificindividual profiles.

Figure 2. The probability of belonging to the 6 profiles by age (the green lineis the average profile probability)

Note that the degree of vertices must be taken into accountas the values of the different parameters are biased by it, wechose to compute profiles separately for each degree anddistributed the vertices of each degree into 6 profiles defined asfollows:

profile 1: densely connected networks: the number ofedges is high and the number of isolated vertices islow; profile 2: sparsely connected networks (the opposite
situation): the number of edges is low and the number
of isolated vertices is high; profile 3: mixed situation where there is a densely
connected group of neighbors (many triangles) and asparsely connected one (many isolated vertices); profile 4: medially dense networks but with many
triangles: these networks do not belong to the first 3
profiles but have a high number of triangles; profile 5: medially dense networks but with manystars: these networks do not belong to the first 4
profiles but have a high number of stars;
 profile 6: medially dense networks with no special
structure: unclassified vertices.
The question is to determine whether there is a connection
between the different profiles and the age of a person or not. To
answer this question, we computed, for each age from 18 to

Figure 3. Hierarchical clustering of ages on probabilities in the 6 connectvity
profilesLet us now group together the ages that have similar
probabilities for the 6 profiles. A hierarchical clustering was
performed on profiles probabilities (see: figure 3). We observe
1

2

The persons older than 60 are underrepresented amongst mobile phone users.

Book of abstracts for NetMob 201012

NetMob - Analysis of Mobile Phone Networks 2010 – communication proposalthat there are 4 main homogeneous age groups very similar tolife stages categories [6]: 18-23 (students), 24-27 (young people
starting their active life), 28-46 (in couple, usually withchildren), and 47-60 (at the final stage/end of professional life,
children are adult or living apart). Interestingly, here theclassification is based exclusively on structural characteristicsof their local communication network (where network size
effect was neutralized).

technological artifact but a more general social interaction
pattern.
The personal networks composition was also scrutinizedlooking at the fraction of men in ego communication network(see figure 5). We observed that the overall gender homophily
in communication networks evolves with age for men and, less,in women’s networks. The life cycle transitions modify
sociability patterns—from external to the household contacts
for young people to more and more family-oriented links forolder individuals [10]—and influences the shape of gender
relations. In fact, as domestic and familial spheres are still
associated with the role of woman, with age the male’s network
starts to be populated by females. At the end of lifecycle, there
are more women than men in the man’s mobile phone
directory.

C. Gender effect in mobile communication networks
The second personal characteristic of people in our networkis their gender. Some years ago, in a French study on theresidential use of the (fixed) telephone, the communication ofseveral hundreds of adult men and women has been followed
for 4 months using telephone billing records [5]. The study
focused on the correlation between the observed duration ofphone calls and the gender of callers and receivers. Data haveshown that the duration of calls are correlated with the genderof the call receiver and is on average longer when a woman iscalled. Therefore the reasons why women speak more on thephone [6] seem more related to the gender homophily intelephone networks than to ―their intrinsic tendency to talk.‖
An in-depth Conversation Analysis work on a recorded
telephone talk’s dataset [7] has suggested that politeness rules
governing the telephone call can explain in part why it is thegender of receiver that has the biggest effect on how the call ismanaged and on its overall duration. The conversations
involving women tended to go through longer introductive
sequences, to be more multi-thematic and digressive in nature
with a corresponding lengthening and multiplication of closure
sequences; and the conversations with men had a tendency to
be linear and monothematic. In summary, the callers seem toadjust their interaction style to the gender of the receiver.

58% males in personal network

56

48
46
44
42
70

65

60

55

50

45

40

35

30

25

20

ego age

Figure 5. Fraction of males in the communication network of females (red)and males (blue) by age

Going back to communication practices, we can speculate
about their hypothetical transformation. Of course, we do nothave long-term time series, thus our interpretation remains
tentative. However, some tendencies (see: figure 6) indicate
differentiation of gendered mobile usages by age. The SMS
usages seem to be more ―feminine‖ in general (fig. 6-a): foryounger part of population (aged 18-25), we also notice that the
between-gender ―texting‖ is particularly popular. And, in fact,
it develops at the expense of voice calls (fig. 6-c); the numberof voice communication is going down in young adults. The
duration of calls varies less, but for the young adults it
diminishes sharply for same gender calls. The mixed-genderconversation length remains at the level of other age groups.

180''
150''
120''
90''
60''
30''

We can consider that in younger generations the mobile
phone appropriation was deeper as it includes bothcommunication functions offered by cell phones: text andvoice. Some authors indicate that heavy SMS use inyoungster’s relation with other gender is related to seduction
tactics where a direct voice contact can be more ―risky‖ forinterlocutors [11]. Anthropologists also emphasized thepropensity of girls to write personal diaries, letters, etc., as well
as women responsibility in familial correspondence [12]. Thechanging balance between voice and text in general and in
between-gender communications can be in part a reflection of

0''
Female to Male

50

75

210''

Male to Female

52

40

Ten years after, the mobile usages still fit this gendercommunication pattern. As we can see in the figure 4, mobile
phone calls towards a woman are, in average, longer than calls
to a man, whatever caller gender is.

Male to Male

54

Female to Female

Figure 4. Mean call duration (in seconds) according to call initiator andreceiver gender

To go further, we isolated all mixed-gender two-way
communication pairs in our network and calculated average
durations of call between them. We obtained 171 seconds whena male calls a female and 162 seconds when a female calls amale. As a consequence, it seems that we do not face a3Book of abstracts for NetMob 201013

NetMob - Analysis of Mobile Phone Networks 2010 – communication proposal

new form of accommodation to a new communication channel
offered by a popular technology.
a.

40

F->F

35

M->F

duration of the call, while the gender of the caller is lessimportant.
We also built ego-centered networks for each customer andtried to find some correlations between the topologicalstructure of their neighborhood and their behavior. Automatic
profiling based only on simple topological properties yieldedgroups of users which correspond to life stages categories.

F->M

Mean SMS nb

30

M->M

25

Much work remains to be done in this context, in particularmore complex network properties and their correlations withage or gender could be studied. We could also propose models
taking such behaviors into account.

20
15
10
5
0
74 72 70 68 66 64 62 60 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18
age

b.

240''

V.

F->F

[1]

F->M

210''

Mean call duration

M->M

180''

150''

120''

90''
74 72 70 68 66 64 62 60 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18
age

c.

9
8
7

Mean call nb

6
5
4
M->M

3

M->F
2

REFERENCES

J-P.Onnela et al., ―Analysis of a large-scale weighted network of one-toone human communication‖, New Journal of Physics, vol. 9, 179, 2007.
[2] C.A.Hidalgo, C.Rodriguez-Sickert, ―The dynamics of a mobile phone
network‖, Physica A, vol. 387, pp. 3017–3024, 2008.
[3] R.Lambiotte et al., ―Geographical dispersal of mobile communication
networks‖, Physica A, vol. 387, pp. 5317-5325, 2008.
[4] R.Ling, The Mobile Connection: The Cell Phone's Impact on Society,
San Francisco, Morgan Kaufman Publ., 2004.
[5] See: http://www.itu.int/ITU-D/ict/statistics/index.html[6] N.Shulman, ―Life-cycle variations in patterns of close relationship‖,
Journal of Marriage and Family, vol. 37, pp. 813–821, 1975.
[7] Z.Smoreda, C.Licoppe, ―Gender-Specific Use of the Domestic
Telephone‖, Social Psychology Quarterly, vol. 63, pp. 238-252, 2000.
[8] L.R.Rakow, Gender on the Line. Women, the Telephone, andCommunity Life, University of Illinois Press, Chicago, 1992.
[9] R.Akers-Porrini, ―Efficacité féminine, courtoisie masculine: la durée
inégale des appels téléphoniques―, Réseaux, vol. 18(103), pp. 143-182,
2000.
[10] A.Degenne, M.Forsé, Introducing Social Networks, London Sage, 1999.
[11] R.Ling, B.Yttri, 2003. "Kontroll, frigjøring og status: Mobiltelefon og
maktforhold i familier og ungdomsgrupper." in F.Engelstad, G.Ødegård
(eds.) På terskelen: makt, mening og motstand blant unge, Oslo:
Gyldendal Akademisk (english version: http://www.richardling.com/
papers/2004_Control_Emancipation_and_status.pdf)[12] D.Fabre (ed.), Ecritures ordinaires, Paris, P.O.L, 1993.

M->F

F->M

1

F->F

0
74 72 70 68 66 64 62 60 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18
age

Figure 6. Mobile communication practices by age and gender: (a) mean
monthly SMS number, (b) average call duration, (c) mean monthly number ofcalls.

IV.

CONCLUSION

We presented here a stage report of an ongoing research.
Based on CDR of a mobile phone operator, we studied therelations between phone usages and networks properties ofcustomer’s and their age and gender. We have shown that somealready known sociological results are still valid in the context
of mobile phone. In particular, there are very different behavior
depending on the age of the users and their gender: the genderof the receiver of phone calls is strongly correlated with the

4Book of abstracts for NetMob 201014

Abstract for NetMob
Authors:
Samuel Arbesman, Harvard Medical School (arbesman@hcp.med.harvard.edu)
Jukka‐Pekka Onnela, Harvard Medical School (onnela@hcp.med.harvard.edu)
Nicholas A. Christakis, Harvard Medical School (christak@hcp.med.harvard.edu)
Presenter: Samuel Arbesman

Geography of Social Groups
The relationship between geographical position and network position within social
networks is a complex one. Previous research has shown that connectedness isinversely proportional to distance, and that tie strength is related to geographicalposition as well. Here we focus on groups of individuals within social networks. By
examining a mobile phone network from a European country, we create a metric of
the geographic span of collections of people, in order to determine the localities ofgroups of individuals. Through the development of a suitable null model, we verify
that locality is indeed a very important component of locality for group structure. In
addition, we find that this span is related to the size of the group in a clearly
quantifiable manner.

Book of abstracts for NetMob 201015

From Wireless Contacts to Community Structures
Theus Hossmann, Thrasyvoulos Spyropoulos, and Franck Legendre
Computer Engineering and Networks Laboratory
ETH Zurich, Switzerland
lastname@tik.ee.ethz.ch
Abstract—Human mobility and resulting contacts are driven
by intention, co-location, and social relations between people.
Based on wireless contact traces (Bluetooth, Wifi), we aim
at characterizing the structure in human contacts. Instead ofinvestigating the microscopic properties of contacts (e.g., durationand occurrence distributions), we are more interested in a macroscopic view of mobility that can more easily capture the range ofhuman inter-relations. We hence turn to community detection.
However, since these algorithms require one-dimensional tie
strength metrics, we present a method to map contacts features(evolving with time) to a scalar feature value. We then analyze
the outcome of the community detection by looking at inter- andintra-community ties. This provides interesting insights on thediversity of human inter-relations, which have applications todiffusion processes, for example.

I. I NTRODUCTION
The rapid proliferation of smartphones with wireless networking capabilities (Bluetooth, Wifi) creates amble opportunity for opportunistic networks where devices connect toother devices in proximity (when within radio range), “onthe fly”, to exchange or spread information. This is a novel
networking paradigm that is envisioned to co-exist with (and
often complement) existing broadband wireless technologies(e.g. cellular, WiFi, etc.). Since actions of interest can only
occur during a wireless contact, contacts and their statisticalproperties become of key importance in the design and performance evaluation of such opportunistic networks. To thisend, a number of efforts have been made recently to collectrelevant mobility data and analyze contact patterns; this isdone either implicitly, by looking at the access points andbase stations users are associated with over time in WiFi or
cellular networks [1], or explicitly with experiments designed
to log peer contacts (e.g. via Bluetooth) [2], [3], [4]. The
majority of these traces reveal a considerable heterogeneity incontact patterns, but also significant structure and (statistical)
predictability of these patterns e.g. due to time-of-day periodicity, location preference, etc. Nevertheless, the vast majorityof trace analysis research in networking has focused on theinter-contact and contact duration statistics [5], [6], which areimportant for network performance analysis but limits mobility
analysis to a microscopic view.
Recently, researcher have been looking at mobility at largescale [1], its predictability [7], and spatial connectivity properties [8]. Human mobility and resulting contacts are actually
driven by intention, co-location, and social relations between
nodes (e.g. friends, colleagues). The latter influences someone
to decide the destination (and often time) of a mobility
trip; location on the other hand dictates the path, as wellas (unknown) nodes encountered regularly at preferred/homelocations (“familiar strangers”) or occasionally (“random encounters”). This creates a rather intricate contact structure thatis not readily observable or usable at contact and inter-contact
pattern levels. To this end, a more abstract, macroscopic viewof mobility is needed that can more easily capture the range
of node inter-relations.
In this abstract, we present a detailed study and comparisonof the community structure of 4 mobility traces, namely the
Haggle trace [2], the MIT Reality Mining trace [3], and theETH trace [4]. We apply a state of the art community detection
algorithm [9] to study the nature of inter-community links(e.g. bridging links vs. bridging nodes vs. community overlap,etc.), and the inter- and intra-community weight distributions
in order to highlight the diversity of human relations. To ourbest knowledge, this is the first in depth comparative study ofthese properties.
In our context, nodes and contacts can be represented ona contact graph, where a link between two nodes indicates ameasured “strong” relationship between nodes (e.g. frequentmeetings, or a recent meeting [10]) through its existence(binary graph) or an edge weight (weighted graph). A variety
of metrics and algorithms could then be used to characterize
node importance on this graph, such as degree centrality,
pagerank, etc., as well as to identify similar nodes through(implicit or explicit) community detection. Yet, the actual“social properties” of mobility traces, such as the modularity of communities and the distribution of inter- and intracommunity weights, have not received the same amount ofattention. These properties are particularly important for two
reasons: first, they allow us to better understand the underlying
structure governing human mobility and facilitate the designof improved mobility models. second, they give hints on theimpact of the social structure on the dynamics of diffusion
processes e.g., in terms of delays but also in terms of capacity(or conductance).
The outline of this abstract is the following. In Section II,
we describe the contact data used for our analysis and how
we pre-process them by mapping and aggregating pair-wisecontacts (i.e., different characteristics evolving over time) to ascalar value suited for community detection algorithms withweighted edges. In Section III, we analyze the outcome of thecommunity detection algorithm. Eventually, we conclude by
discussing ongoing work in Section IV.

II. DATA D ESCRIPTION
We start by describing the data used for our analysis in
Section II-A. We then describe a metric of tie strength basedon the principal component of contact frequency and duration(Section II-B).

Book of abstracts for NetMob 2010

16

2

1
1.5

2

1

0.5

0.5
0

0

100

200

300

400
500 600# Contacts

700

800

900

0

1000

0

50

100

150

(a) MITTABLE I

5C ONTACT TRACES CHARACTERISTICS .

4.5

6

5

(b)
4

ETH
INFO

105
xx 10
3.53

MIT

x 10

200
#C

6

3
2.5

5

2.5
2

4

SW

x 10

INFO
41 conference
participants
3 days
120s (Bluetooth)ETH
20 lab students and staff
5 days0.5s (WiFi)

1000 000
10 030220 459

230 000
10 150Tot.
Tot.Time
Time[s][s]

MIT
97 campus students and staff
9 months
300s (Bluetooth)

Tot. Time [s]Scale and
context
PeriodPeriodicity# Contacts
Total
Per dev.

3
2.5
2

2
1.5
1.5

1
1.5

3

2

1

1

0.5
0.5

0.5

547

Tot. Time [s]

4
3.5

0

0

100

200

300

400
500 600# Contacts

700

800

900

1

000
0

1000

50
20

100
40

(a) MIT

150
60

200
250 120300
80
100
Contacts## Contacts

350
140

400
160

450
180

500
200

0
0

50

# Co

(b) INFO
ETH(c)(a) MIT(b) INFO
SWISS

4

x 10

(d) S
4

A. Contact Traces
Fig. 1. Scatter-plots of number of contacts vs. total contact duration overWe define a contact as the period of time during which the whole duration of the traces.
two devices are within radio transmission range of each other.
A contact contains of the information about the two nodes define the tie strength between i and j asT the projection of
involved, a starting time and a duration. In a opportunistic zi,j on the principal component, wi,j = e1 zi,j + wmin , where
network, such a contact is an opportunity to exchange or we add wmin – the smallest tie strength of all node pairs – inorder to have positive tie strengths. With this metric we are
spread information.
In order to cover a broad range of mobility scenarios with able to combine the frequency and duration in a scalar value
the heterogeneity of node pairs.(e) We
TVCM
our analysis, we use different measured contact data: the that naturally (c)represents
INFO
can
now
definetheweightmatrix W with (d)theSWISS
respective wi,jover. the whole duration ofFig. 1. Scatter-plots of number of contacts vs. total contact duration
MIT Reality Mining [3] (MIT), the iMotes Infocom 2005
Note that with this aggregation of the contact data, we loose(INFO) [2] and the ETH [4] (ETH). Their characteristics arethetiming information about contacts. We are not so muchsummarized in Table I. Note that in the MIT trace, despite
interested
in the actual timing of the contacts, but rather try
its long duration, a lot of short contacts were supposedly
not logged due to its time granularity of 5 minutes. For our to capture the underlying structures that govern mobility.
The number of communities and the resulting modularity isevaluation we cut the trace at both ends and used 1000 000
given
for each contact trace in Table II.
contacts reported between September 2004 and March 2005.
Note that this time period contains holidays and semester
III. C OMMUNITY S TRUCTURE A NALYSIS
breaks and thus still captures varying user behavior. The ETH
We will now focus on the(e) TVCM
community structure of humantrace contains more than 230 000 reported contacts and isFig. 1. contacts
Scatter-plots of numberof contacts vs.Using
total contact duration
over the whole duration
the trace. as Spectral
contacts.
the Louvain
as ofwell
unique in terms of time granularity and reliability. Althoughcommunity detection algorithm and the Newman modularity
its measurement period spans a considerably shorter time than
metric, we will first (Section III-A) assess how strongly moduMIT, we have on average more than 1000 reported contacts
lar contacts are. In a second step (Section III-B), we will focus
per device. This is roughly the number of contacts per device
on the the conductance between the communities, and assess
we also have for the MIT trace.
how strongly communities are connected to other communities
and how the conductance between them is distributed (i.e.,
B. Tie Strength
bridging links, bridging nodes or hierarchical overlap).
To assess the strength of the tie between two nodes in a contact graph different metrics such as the age of last contact [11], A. Intra-Community Ties
contact frequency [12], [13] or aggregate contact duration [13]In order to assess the modularity of a given partition ofhave been used (i.e., in DTN routing protocols). Here we con- nodes to communities we compute the widely used Q function
sider two features: contact frequency1 and aggregate contact as introduced by Newman [15]. The Q function
duration. In a first step, we assign each pair of nodes {i, j}


ki kj
1 X
a two-dimensional feature vector zi,j = (fi,j , di,j ), where fi,jwi,j −
δ(ci , cj ),Q=is the number of contacts in the trace between nodes i and j,
2m ij
2mand di,j is the sum of the durations of all contacts between thePki =two nodes – both dimensions centered (zero empirical mean) where
j wi,j is the strength of node i and m =P1
and normalized to their respective standard deviation.
k
is
the
total
weight in the network. ci denotes thejj2
Figure 1 shows the scatter plots of the number of contacts community of node i thus, the Kronecker delta function
vs. the total contact duration (pair-wise) for the MIT and INFO δ(ci , cj ) is one if nodes i and j share the community andtraces. They clearly show a high correlation between both zero otherwise. Q = 0 is the expected quality of a random
features.
community assignment and [15] reports modularities of above
Since state-of-the-art community detection requires one- Q = 0.3 for different networks (social, biological, technical,
dimensional tie strength metrics, we transform the two- etc.) for state-of-the-art community detection algorithms2 .
dimensional feature vector to a scalar feature value: We use the
In Table II we present some statistics of the trace networks’principal component (e.g., [14]), i.e., the direction in which community structure as found by Louvain. A first thing to notethe data vector Z has the largest variance the direction of the is that the two clustering algorithms find different communities
Eigenvector e1 with the largest corresponding Eigenvalue. We but with similar modularity. In general the modularity of the
6

INFO

x 10

3

Tot. Time [s]Tot. Time [s]

2.5

2

1.5

12

5

10

4

8

Tot. Time [s]

5

3.5

3

TVCM

x 10

6

4

2

1

0
0

2

1

0.5

20

40

60

80

100 120# Contacts

140

160

180

0
0

0
0

50

100

100

200

# Contacts

4

12

200

300
150
# Contacts

TVCM

x 10

10

Tot. Time [s]

8

6

4

2

0
0

100

200

300
# Contacts

400

500

600

2 Note that the quality of a community assignment is a function of (i) the
network, since it can be more structured or less, and (ii), the community
detection algorithm, since it can find a good community assignment or not.

1 Note that contact age – assuming a stationary contact process – can beconsidered an approximation of contact frequency, therefor we do not consider
it here explicitly.

2Book of abstracts for NetMob 2010

17

400

500

600

Trace/Model
MIT
ETH
INFO

# Comm.
5
2
6

Q
0.49
0.23
0.12

the nodes. However, between them there is only 1% of theweight.
IV. D ISCUSSION AND C ONCLUSIONS
The results presented herein are preliminary investigationsof using community detection algorithms to highlight thecommunity structure of contact traces. Actually, it does not
only matter how much of the weight falls between two
communities, but also how this weight is distributed. Thus,
we are currently aiming at identifying the type of interface as
either (i) bridging links (people linked to one specific person
in another community), (ii) bridging nodes (people part of two
communities i.e., overlap), or (iii) hierarchical communities.
We characterize these three types in the following.
Note that certain community detection algorithms inherently
identify some of these interfaces. For instance the K-Cliquealgorithm [16] allows nodes to be in more than one community
and thus identifies bridging nodes. Similarly, a class of algorithms such as Newman Girvan [17] is based on a hierarchicaltree (dendrogram) and thus inherently identifies hierarchies.
However, neither of them provides a distinction between all
the three types of inter-connection. We are hence currently
combining the peculiar features of existing algorithms at once.

TABLE IIN UMBER OF COMMUNITIES AND MODULARITY (Q) OF CONTACT TRACESUSING THE L OUVAIN ALGORITHM .

5

2.5
2

3
WeightWeight

4

2
1
0
0

1.5
1
0.5

10

20

30

40

50

Rank

0
0

5

10

15
Rank

20

25

30

(b) MIT, Node 41(a) ETH, Community 1

Fig. 2. Ranked Community Internal Weights (per Community and per Node).

Louvain communities is slightly higher communities than theSpectral. In the rest of the paper, we will present all results
for the Louvain algorithm, though, the results hold also for
the Spectral clustering. Second, the modularity varies broadly
among the traces. We observe a strongly modular MIT trace,
lower modularity in the ETH case and very low modularity in
the INFO case. Similar values for other community detection
algorithms (K-Clique and Newman), different traces and otherstrength metric (total contact duration) have already beenreported in [13], thus we confirm these findings as a first result.
To find out more about the insides of communities welook at the distribution of intra-community weight. Figure 2
shows some typical representatives of community-internal tie
strengths, ranked over all node pairs of a community, as wellas per node. We observe that the weights are strongly skewed.
A community can thus not be thought of as a homogeneousgroup of strongly connected nodes (like a mesh). Instead, there
is strong heterogeneity even within a community. This observation is consistent throughout all traces and all communities(only few are shown in Figure 2 due to space limitations).

R EFERENCES[1] M. C. Gonzalez, C. A. Hidalgo, and A.-L. Barabasi, “Understanding
individual human mobility patterns,” Nature, vol. 453, no. 7196, pp.
779–782, June 2008.
[2] P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot,“Pocket switched networks and human mobility in conference environments,” in WDTN, 2005.
[3] N. Eagle and A. Pentland, “Reality mining: sensing complex social
systems,” Personal and Ubiquitous Computing, May 2006.
[4] V. Lenders, J. Wagner, and M. May, “Measurements from an 802.11b
mobile ad hoc network,” in EXPONWIRELESS, 2006.
[5] V. Conan, J. Leguay, and T. Friedman, “Characterizing pairwise intercontact patterns in delay tolerant networks,” in ACM Autonomics,
October 2007.
[6] T. Karagiannis, J.-Y. Le Boudec, and M. Vojnovic, “Power law andexponential decay of inter contact times between mobile devices,” in
MobiCom ’07: Proceedings of the 13th annual ACM international
conference on Mobile computing and networking. New York, NY,
USA: ACM, 2007, pp. 183–194.
[7] C. Song, Z. Qu, N. Blumm, and A.-L. Barabasi, “Limits of predictability
in human mobility,” Science, vol. 327, no. 5968, pp. 1018–1021,
February 2010.
[8] P. Wang and M. C. Gonzales, “Understanding spatial connectivity of
individuals with non-uniform population density,” Philosophical Transactions of The Royal Society A, vol. 367, pp. 3321–3329, August 2009.
[9] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fastunfolding of communities in large networks,” J.STAT.MECH., 2008.
[10] T. Hossmann, T. Spyropoulos, and F. Legendre, “Know thy neighbor:
Towards optimal mapping of contacts to social graphs for dtn routing,”
in Infocom 2010. IEEE, March 2010.
[11] H. Dubois-Ferriere, M. Grossglauser, and M. Vetterli, “Age matters:
efficient route discovery in mobile ad hoc networks using encounter
ages,” in MobiHoc, 2003.
[12] A. Lindgren, A. Doria, and O. Schelén, “Probabilistic routing in intermittently connected networks,” SIGMOBILE Mobile Computer Communications Revue, July 2003.
[13] P. Hui, J. Crowcroft, and E. Yoneki, “Bubble rap: Social-based forwarding in delay tolerant networks,” in MobiHoc, May 2008.
[14] R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification (2nd
Edition). Wiley-Interscience, November 2000.
[15] M. E. J. Newman, “Modularity and community structure in networks,”
Proceedings of the National Academy of Sciences, June 2006.
[16] G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,”
Nature, June 2005.
[17] M. E. J. Newman, “Analysis of weighted networks,” 2004.

B. Inter-Community Ties
Comm.
Index
1
2
3
4
5

1

2

3

4

5

20.5%
1.0%
0.5%
0.1%
0.01%

1.0%
31.8%
4.2%
2.9%
0.2%

0.5%
4.2%
13.4%
2.7%
0.2%

0.1%
2.9%
2.7%
8.9%
0.1%

0.01%
0.2%
0.2%
0.1%
2.1%

TABLE IIIP ERCENTAGES OF TOTAL WEIGHT WITHIN AND BETWEEN COMMUNITIES(MIT TRACE ). A LL WEIGHTS SUM TO 100% AND INTER - COMMUNITYWEIGHTS ARE HALVES BETWEEN TIED COMMUNITIES .

We now change our focus on the interface between thecommunities. Table III shows an example matrix for the MIT
trace of how the total weight in the network is distributed
within the communities and between the communities. In
the matrix we see that the inter-connections of communities
are weak in many cases. For instance, communities 1 and 2
together contain more than 50% of the weights and 50% of
3Book of abstracts for NetMob 201018

Social Relationship and Behavior Analysis in Mobile
Social Networks
Huiqi Zhang, Ram Dantu

Department of Computer Science and Engineering
University of North Texas
Denton, TX 76203 USA

huiqizhang@my.unt.edu, rdantu@unt.edu

I.

INTRODUCTION

The modern telecommunication, such as mobile
communications, unites people around the world into a WideArea Social Network (WASN). In WASN, people form groups
or clusters based on interests, goals, etc. Since the mobile
phones have become an important tool of modern human daily
life, telecommunication patterns may reflect different humanrelationships
andbehaviors,andchangesintelecommunication patterns may expose signs of social
relationships and behavior changes. For example, the calling
patterns of a person with his/her friends differ from those withspammers.
A social network dynamically changes since the social
relationships (social ties) change over time. The evolution of asocial network mainly depends on the evolution of the social
relationships. The social-tie strengths of person-to-person are
different one another even though they are in the same groups.
Almost all existing social network research has focused on
overall social-network structures and properties. These
research efforts lack analysis for one-to-one or one-to-many
relationships and behaviors in the detail-necessary wheninterested in special groups or clusters of people. These
detailed features of human relationships are more importantfor detecting terrorists, spam and user preferences. Because ofhuman social-behavior’s diversities and complexities,
applying one technique will not detect the many different
features of human social behaviors. Therefore, we use
multiple probability and statistical methods, integrating themfor social-network and human-behavior analysis. We propose
an integrated platform for analyzing the properties of social
structures and human behavior; for quantifying and measuring
interpersonal relations in groups; for predicting social ties; fordetecting change points, unusual consumption events, opt-in
bursts; and for identifying willingness levels of users tocommunicate each other based on human telecommunication
patterns.
The integrated platform consists of several components
including zoom, scale, and analysis tools, which are used foranalyzing network structures, for discovering social groups
and events, for quantifying relationships and so on. The
integrated platform is extensible; new tools can be added asneeded. By zoom-in we may use multiple scales to analyzesocial-group member behavior up to one-to-one. By zoom-out
we may analyze general social-network structures andproperties.
Pentland uses the mobile phones programmed, electronic
badges and microphones as a Socioscope to sense and capture

human behavioral data (location, proximity, body motion) [9],[10]. These behavioral data are then used to analyze thecharacterization of group distribution and variability,
conditional probability relationships between individual
behaviors and focuses on human relationship analysis basedon physical distance proximity. Eagle extends the approach in[9], [10] to study a variety of human cultures as a culture lens[11]. Eagle et al. present a method for measuring humanbehavior, based on contextualized proximity and mobile
phone data, to study the dyadic data using the nonparametricmultiple regression quadratic assignment procedure (MRQAP)[2]. Our approach focus on quantifying human behaviors,interpersonal relationships, changes of relationship bystudying human calling patterns based on mobile phone calldetail records.
II. OVERVIEW OF THE PROPOSED APPROACH
As presented in Figure 1, the integrated platform consists ofa number of components, including data extraction andtransformation; network visualization; and zoom, scale, andseveral analysis tools used for analyzing network structures,
discovering and quantifying social groups, predicting social
ties and detecting events, quantifying relationships, etc. The
integrated platform is extensible. New tools can be added as
we identify additional features. The model is composed of thethree layers briefly described below.
Data Processing: This layer consists of two components:
Data Extraction and Data Transformation. In data extraction,
related information is extracted from raw datasets and thentransformed in data transformation into required data format
for visualization and analysis.
Visualization and Zooming: An open-source visualization
tool is used for drawing the social networks. Using zoomingin levels we may use multiple scales to analyze social-groupmember behavior up to one-to-one. Using zooming-out levels
we may analyze general social-network structures andproperties.
Behavior Analysis and Detection Tools: This layer, the coreof the model, consists of four components: Quantifying Social
Groups, Reciprocity and Predicting Social Ties, Change Point
Detection and Unusual Consumption Detection, Opt-in
Pattern Detection and Willingness Level inference.
We describe these components and solutions in details next.

Book of abstracts for NetMob 201019

Dataset
Data Processing
Data Extraction
Data Transformation

Zoom in

Visualization and Zooming

Behavior Analysis and Detection Tools
Relationships

EventsPatterns

GroupsChange Points

Opt-inUnusualConsumption

Willingness

Reciprocity
Predict Tie

Results
Fig.1 The architecture of the proposed approach.

III. QUANTIFYING GROUPS AND PREDICTING TIESThe approach proposed here for the social-group
identification relies first on a computation of a reciprocity
index. We then use the index to compute the affinity between
two users. Finally we use this affinty to define the sociallyrelated groups. These steps are presented in the next Sections.
A. Dyads and Reciprocity Index:
In social networks, one of the important relationships
between people is reciprocity. Reciprocity can be defined as
the action of returning similar acts [1], [5]. In this study, ourinterest is to investigate how people use technology toconstruct social relationships.
In [5] the authors propose the index of mutuality, ρ kp . This
index focuses on the probability of a mutual choice between
two actors i and j in a graph.
Our approach for reciprocity differs from the above work.
We observed that the structure and transactions in reciprocity
are different when compared with face-to-face interactions.

Existing approaches measure the tendency of mutual choices
for actors (nodes) in a graph. These approaches do not deal
with frequency and duration of real-time electronic
communications between two actors. In real life, the frequency
of communication plays an important role in the relationshipbetween persons. To the best of our knowledge no similar
work has been reported. We propose a new reciprocity index
based on mobile-phone call-detail records.
In a mobile-phone social networks, actor i and actor j may
call each other multiple times. Reciprocity reflects theirrelationship in a period of time. The mutual index in [5] andother existing mutual indices cannot measure this kind of
relationship. The existing mutual (reciprocity) indices measure
the tendency of mutual choices for actors (nodes) in a graph.
They do not deal with communication frequency. We proposea reciprocity index, ρ a↔b which does measure the tendency ofreciprocity for actors a and b in a group.
Suppose that the number of phone call arrivals is a Poissonprocess. Then the probability of no arrivals in the interval [0,t] is given byP(τ > t ) = e − λtwhere λ is the arrival rate and τ is interarrival time. The
occurrence of at least one arrival between 0 and t is given by
P (τ ≤ t ) = 1 − e − λtConsidering actor a calls actor b at time ti with rate λa t ,the probability of actor b calling actor a back (reciprocity) at atime t j with rate λb t can be computed by

P (a → b & b → a ) = P (a → b) P (b → a | a → b)not
= P (a → b)[ P (b → a ) + ρ a ↔ b P (b →a )]− λ (t −t )− λ (t −t )= (1 − e − λ a t i )[(1 − e b j i ) + ρ a ↔ b e b j i ]The expected value, E ( R | ρ a ↔b ) , of number of reciprocity
from b to a is the total number of calls, S, from a to b times
this probability, i. e.
− λ ( t −t )− λ ( t −t )E ( R | ρ a ↔b ) = S (1 − e − λati )[(1 − e b j i ) + ρ a ↔b e b j i ]After rearranging the terms, we have− λ ( t −t )− λ ( t −t )
ρ a ↔b = [ R − S (1 − e − λati )(1 − e b j i )] / S (1 − e − λati )e b j i (1)where R is observed number of reciprocity.
The ρ a↔b is 0 if there is no tendency toward reciprocity and1 if there is a maximal tendency toward reciprocity.
B. Social Group Identification
Groups correspond to data clusters. Cluster analysis
concerns a set of multivariate methods for grouping data
variables into clusters of similar elements. In our work we use
probabilistic models for classification of variables by theiraffinity [3].
Affinity measures the similarity between probability
distributions. Because our problem belongs to discrete events,
we only consider finite event spaces. LetNS N = {P = ( p1 , p2 ,... p N ) | pi ≥ 0, ∑ pi = 1}
i =1

be the set of all complete finite discrete probability
distributions and P, Q ∈ S N . The Hellinger distance between
P and Q is defined as

Book of abstracts for NetMob 2010

20

1 N
∑ ( pi − qi ) 2
2 i =1d H2 ( P, Q) ∈ [0,1] , d H2 ( P, Q) = 0 if P = Q andd H2 ( P, Q) = 1 if P and Q are disjoint [3].
The affinity between probability measures P and Q isdefined asd H2 ( P, Q) =N

A( P, Q) = 1 − d H2 ( P, Q) = ∑ pi qi
i =1

A( P, Q) ∈ [0,1] , A( P, Q) = 1 if P = Q and A( P, Q) = 0 if P and
Q are disjoint [3].
We clasify our social network members into three
categories: socially close members, socially near members andsocially far members.
In this paper, we use three attributes incoming (in),outgoing (out) and reciprocity (reci) of calls and messages.
Let mi , ni be the number of calls, wherei ∈ {in, out , reci} . P = ( pin , pout , p reci ) is a vector of
normalized frequencies over the training period.
Q = ( qin , qout , q reci ) is a vector of normalized frequencies ofthe same attributes observed over the testing period. Thenpi = mi ∑i mi where i ∈ {in, out , reci} andqi = ni∑ n where i ∈{in, out , reci} .
ii

The reciprocity part is computed by Eq. (1).
We compute affinity between P and Q is as follows:A( P, Q ) = ∑i pi q i where i ∈ {in, out , reci} (2)C. Predicting Social Ties
We map call-log data into time series (social-tie strengths)
by our affinity model and apply Seasonal Auto Regressive
Integrated Moving Average (SARIMA) models for predicting
the future values.
Seasonal Auto Regressive Integrated Moving Average(SARIMA) models integrate Seasonal (periodic), AutoRegressive (AR), Integrated (I), and Moving Average (MA)
into a general comprehensive time series model [12].
The seasonal ARIMA( p, d , q) model with period s is given as
φ p ( B )Φ P ( B s )∆d ∆Ds Z t = θ q ( B )ΘQ ( B s )etor
φ p ( B )Φ P ( B s )(1 − B ) d (1 − B s ) D Z t = θ q ( B )ΘQ ( B s )etwhich are denoted by SARIMA( p, d , q) × ( P, D, Q) s .
The Box-Jenkins method [12] uses an iterative approach of
identifying a possible model from a general class model. The
chosen model is then checked against the historical data to see
whether it accurately describes the series. The model fits well
if the residuals are generally small.
IV. EVENT DETECTION
Another important element that we can extract from callrecords is the occurrence of events. This capability could be
used for detecting network attacks. To identify events in thecall records we first use a wavelet de-noising method toprocess the data and then we apply the modified method

described in [6] for detecting change points based on numberof calls and call durations. These steps are described next.
Social network structures and relationships dynamicallychange over time. Still, change point and event detection
methods can be used to discover human relationship andbehavior changes based on human communication patternchanges.
A. Wavelet Denoising
Generally, for the denoising, the wavelet scaling function
should have properties similar to the original signal. The
general wavelet denoising procedure follows 3 steps: wavelet
selection, threshold selection and inverse wavelet transform.
In a Discrete Wavelet Transform (DWT) the scale factors
between levels are usually chosen to be powers of 2. For
DWT, the mother wavelet is defined as:ψ j ,k (t ) = 2 − j / 2ψ (2 − j t − k )where j, k є Z.
The DWT is given by
W j .k = 2 − j / 2 ∫∞−∞x (t )ψ ( 2 − j t − k ) dt

where W j ,k is wavelet coefficients, x(t) is the signal to betransformed, and ψ(t) is the mother wavelet or basis function.
The inverse transform of DWT used to compute original
data is given as:∞∞x(t ) = ∑ j =1 ∑k∈Ζ W j ,kψ j ,k (t ) + ∑ j =1 c j ,kφ j ,k (t )where φ j ,k (t ) denotes the scaling function and c j ,k denotes
scaling coefficients, which are defined by∞

c j ,k = 2 − j / 2 ∫ x(t )φ j ,k (2 − j t − k )dt−∞

The inverse wavelet transform (IWT) reconstructs the signal
from its coefficients.
B. Change Point Detection Procedures:
A change-point analysis method attempts to find a point
along a distribution or trend of values where the characteristicsof the values before and after the point differ.
Let X = ( X 1 , X 2 ,..., X θ ) be a process.
The multiple change points for the process is defined as [6]X 1 = ( x1 ,..., xτ1 ) ~ f1

X 2 = ( xτ1 +1 ,..., xτ 2 ) ~ f 2.................................
X θ = ( xτθ −1 +1 ,..., xτθ ) ~ fθ

where f1 , f 2 ,..., fθ are either known or unknown probability
density functions or trends; τ 1 ,τ 2 ,...,τ θ −1 are change points.
We first use a wavelet-denoising method to pre-process thedata, and then we use a sequential estimation scheme in [6] fordetecting multiple change points which chooses increasing
subsamples and finds one change point at a time until allchange points are found.
The general procedure for change point detection is asfollows.
a) Sequential Detection:
A widely used change-point-detection method based on
Page’s cumulative sum (cusum) rule is defined by
T ( a ) = inf{n : S n ≥ a}Book of abstracts for NetMob 201021

whereg ( xi )S n = max ∑i = k +1 log
1≤ k ≤ nf ( xi )n

is maximum likelihood ratio based cumulative sum, a is a
threshold, and f and g are pre- and post-change density
functions. When density functions are unknown, the best
estimates for each value k of a change point are used. The
cusum is computed byngˆ ( xi )Sˆn = max ∑i = k +1 log
1≤ k ≤ nfˆ ( xi )and the stopping rule described in [39], defined byTˆ (a ) = inf{n : Sˆn ≥ a}
We use a leased-squares method for nonlinear trends.
Whether a trend is linear or exponential is decided by thelower sum of squares for each segment. In this way, themaximum likelihood ratio is replaced by a minimum weighted
sum of squared residualskSˆn = min{∑i =1knfˆi ( xi − fˆi ) + ∑i = k +1

gˆ i ( xi − gˆ i )}and the stopping rule is defined asTˆ (α ) = inf{n : pn ≤ α }where pn is a p-value testing significant based on Ŝ n of achange point at k.
b) Post-estimation:
The detected change point must be estimated after astopping rule has detected it. The change point estimator weuse is based on the cusum stopping rule Tˆ and the minimum pvalueτˆ = arg minˆ p (k , Tˆ , X )1≤ k <T

where p(k , Tˆ , X ) is the p-value of the likelihood ratio testcomparing X 1 = ( x1,..., xk ) and X 2 = ( xk +1,..., x ˆ ) .
Tc) Significance Tests:
To eliminate false change points, we use ANOVA F-type
tests. If the test is significant, we repeat step 1-3 to search fornext change point, else, the test is a false change point and thesearch continues based on an initial sequence after the lastsignificant change point.
For fitting linear trend E ( xi ) = a + bti , we use a standard
least-square estimate∑bˆ = i( xi − x )(t i − t )∑ (t − t )iand aˆ = x − bˆt

2

C. Unusual Consumption Event Detection
Change-point-detection methods do not deal with bursts ofshort width in time series. Bursts in time series are related toevents such as attacks in networks. We propose theinhomogeneous Poisson model for detecting these bursts,
which we term as unusual consumption events.
We assume that the number of calls follows aninhomogeneous Poisson process and call duration follows aninhomogeneous exponential distribution.
The maximum likelihood estimates are used to estimate
average number of calls and call duration. Next we consider
the maximum average number of calls and call duration
obtained for all weekday/weekend and week by week.
Suppose that the m week data is used to compute the rates ofnumber of calls and call duration for user p. Let
λˆdp1 , λˆdp 2 ,..., λˆdp 7 be the rate of number of calls obtained for allp
weekday/weekend and λˆwp1 , λˆwp 2 ,..., λˆwm
be the rate of callduration obtained week by week for m weeks of user p
respectively. Let µˆ dp1 , µˆ dp2 ,..., µˆ dp7 be the mean of calldurationobtained for
all weekday/weekend andp
be the mean of call duration obtained weekµˆ wp1 , µˆ wp2 ,..., µˆ wm
by week for m weeks of user p respectively.
Then the maximum means of the number of calls and callduration are respectively computed by:
p
p
λˆmax
= max(λˆdp1 , λˆdp 2 ,..., λˆdp 7 , λˆwp1 , λˆwp 2 ,..., λˆwm)pp
= max(µˆ dp1 , µˆ dp2 ,..., µˆ dp7 , µˆ wp1 , µˆ wp2 ,..., µˆ wmµˆ max)pp
and µ̂ max
are the maximum likelihood estimates ofwhere λ̂max
number of calls and the call duration for user p over thenumber of days specified respectively. The thresholds define
the limits for all weekday/weekend and week by week. Our
assumption is that the calling pattern could be different. Eachcaller has his/her own thresholds, and if the number of calls orcall duration is greater than their usual thresholds for someday, we define that some event has occured in that day.
To calculate the threshold of number of calls for user p,p, we define
N thresppp
N thres= λˆmax+ σˆ maxiand for fitting exponential trend E ( xi ) = exp(a + bti ) − 1 , we usebˆ =We select a Coiflets5 wavelet and the Minimax thresholdmethod to denoise the data by the principles described above
and, then, apply the sequential change point detection methodin [6].

∑i log(1 + xi )(ti − t )∑i (ti − t )and aˆ = log(1 + x) − bˆt

for initial approximation.
When the preliminary estimator of a change point isobtained, we perform a refinement of this estimator by leastsquare fitting from the segment in the neighborhood of thepreliminary estimator. If the change points are not significant
for the chosen level α, they are removed and thecorresponding segments merged.
After the iterations end, all the change points are significant
at the chosen level α.

ppwhere λ̂max
and σˆ max
are the maximum rate of number of callspand correspondent standard error with positive σˆ max.
p
To calculate the threshold of call duration for user p, Dthres,
we definepppDthres= µˆ max+ δˆmax
where µ̂ p and δˆ p are the maximum mean of call duration

max

max

p
and correspondent standard error with positive δˆmax.
Definition of an unusual consumption event
A collection of call-log data can be represented as
C =< (t1 , a1 , d1 , l1 ), (t2 , a2 , d 2 , l2 ),...(t n , an , d n , ln ) > ,Book of abstracts for NetMob 201022

where ti is a time point, d i is a call duration, li is a location
and ai is a pair of actors, caller-callee < si , ri > where si is anactor who initiates a call at time ti and ri is an actor who
receives the call. An unusual consumption event is defined asa subset E ⊂ C of a tuple

We define the opt-in bursts as dense sequences ofaccumulated impulses with an interval of length w.
Let B={b 1 , … b k } be a subsequence of bursts contained in asequence S ={s 1 , …, s n }. The ith burst value is defined aswibi (t ) = ∑ stδ (t − t ij )E = {(t1 , a1 , d1 , l1 ), (t 2 , a2 , d 2 , l2 ),...(t m , am , d m , lm )}such that either ∑d > Dthres or count (d i ) > N thres defined
i =1 im

as the above in the time period ∆t = t m − t1 .

j =1

where w i is total number of impulses of the ith burst, i.e. theith burst width, t j is the occurrence point of the jth impulse ofi

the ith burst and δ(t) is a delta function denoting the

V. PATTERN RECOGNITION
Opt-in is an approach to e-mail or phone marketing inwhich customers must explicitly request to be included in an
e-mail or phone call campaign or newsletter. In addition,customers can easily choose to be removed from a mailing orphone list if the advertisements are unwanted, thus eliminating
unsolicited emails or phone calls. People may be interested insome advertisements for a period of time, but will not wantreceive those advertisements later. Ultimately, the customer
comes to consider this traffic as spam and decides to opt-out.
We believe that current spam filters have great difficulty
detecting this type of traffic. Note that several kinds of opt-ins
exist. We consider opt-ins whom customers show lot interest
for a short period of time and later have no interest but still
keep getting unwanted emails or calls as opt-in bursts.
Another instance where researchers and developers can findpattern recognition useful occurs with presence awareness. We
propose use of a Bayesian inference model to compute thewillingness level of people’s communications with one
another at a given time. Another example of willingness levelof people’s communications is a computer andtelecommunication presence. Emergency of presence-aware
communications allows people to quickly connect with others
via the best choice of communication mean, whether on theroad, in meetings, or working from remote locations. Presenceawareness also lets users know when others in their contact
list are online. For those interested in studying presenceawareness, presence information can include more user
details, such as availability, location, activity, device
capability and other communication preferences. Researchersand developers can use presence to detect and convey
willingness and ability to talk on the phone. Presence-enabled
telephony services can reduce telephone traffic, as well as tag
and improve customer satisfaction. The existing approaches
provide presence for “online,” “busy,” “away,’’ “offline,” etc.
A. Opt-in Detection
Opt-in burst detection is related to burst detection on data
streams and to time series which are continuous data.
However, the Opt-in behavior resembles accumulated
impulses and is not continuous. The existing approaches todetect bursts are used for text, novel and unusual data points
or segments in time-series that either have contents or are
traffic data. However, none of the previous work focuses on
the specific problem we study here, opt-in bursts by studying
the calling pattern based on call detail records to detect opt-in
bursts that reflect human activity.

occurrence of a impulse at point t= t j .
i

The ith burst amplitude A i can be calculated as

Ai =

1 wi
∑ stδ (t − t ij )wi j =1

where s t is the value of an pulse at point t.
To detect the bursts, we define the sliding window SW k as
SWk (t ) = Ak rect (t − tmτk)where A k is the amplitude of a sliding window k,rect((t-t m )/τ k ) is rectangle function denoting the occurrence
point of a burst at time t=t m and τ k is the width of a sliding
window k.
Definition of an opt-in burst
A collection of call log data can be represented as
C =< (t1 , a1 , d1 , l1 ), (t2 , a2 , d 2 , l2 ),...(t n , an , d n , ln ) > ,where ti is a time point, d i is a call duration, li is a location
and ai is a pair of actors, caller-callee < si , ri > where si is anactor who initiates a call at time ti and ri is an actor who
receives a call. An opt-in burst is defined as a subset E ⊂ C ofa tuple E = {( t1 , a1 , d1 , l1 ), ( t2 , a2 , d 2 , l2 ), …,( tm , am , d m , lm ) } such that 0 < count (d i ) < N thres in the time
period ∆t = t m − t1 , where N thres is a threshold which can be
estimated from the historical data.
We process the sequence S by Exponentially Weighted
Moving Average (EWMA), and then apply the dynamic-size
sliding windows to detect opt-in bursts. The EWMA places
more emphasis on the most recent data. Therefore, EWMA
would be more useful in dynamic systems.
Let S ={s 1 , …, s n } be a sequence. Then the moving
average (MA) is given by
k
1
sk =
si
∑
M i = k − M +1
where sk is moving average of the k’s instance and M is thenumber of latest values. The EWMA can be derived from MA
assk = (1 − α ) sk + α (1 − α ) sk −1 + α 2 (1 − α ) sk −2 + α 3 sk −3
where 0 ≤ α < 1 is a constant. This is a recursion function.

Book of abstracts for NetMob 201023

B. Willingness Level Inference
When callers want to make a call, they would like to know
if the callee is in a mood to receive a call. In other words,
callers would like to know when it is a good time to call theparticular callees. We estimate the chance that a callee will
accept a call based on the time of the day, call duration and thelocation.
We propose a Bayesian inference model to compute a
receiver’s willingness level in a given time.
Let X and Y be two events. We have Bayes’ theorem [8]:P (Y | X ) P ( X )P( X | Y ) =P (Y )
P(X | Y) is called posterior probability, P(Y | X) is referred
to as likelihood and P(X) is prior probability.
Let X = (incoming call = accept, incoming call = missed)
Let Y = ( Ti , D j , Locl ), where Ti is time interval, i = 0, 1, 2,…23, (e.g. : 0 – 1 O’clock), D j is a day, j=1,2, …, 7, i.e.,
D1 =Sunday, D2 =Monday, … D7 = Saturday, Locl = location
name, l=1, 2, …n
Then, by Bayes theorem, the willingness level to accept a callisdetect all the different features of human social behaviors.
Thus, we used multiple probability and statistical methods.
We propose a new reciprocity index for measuring thelevels of reciprocity between users and their communication
partners, propose affinity model for quantifying social groups,
map call-log data into time series and apply SARIMA model
for predicting social ties, combine wavelet denoising andsequential detection for detecting change points, propose
inhomogeneous Poisson and inhomogeneous exponential
model for detecting unusual consumption events, combine
dynamic slide window and exponentially weighted moving
average for detecting opt-in bursts and propose Bayesianinference model for quantifying willingness levels.
We may quantify relationships for a short-term period, say amonth, or a long-term period, say, a year or more, using ourmodel by adjusting the parameters. Errors appear when thenumber of calls is small. However, these kinds of cases
seldom occurred in our experiments.
This work is useful for homeland security and for detecting
unwanted calls, e.g., spam, telecommunication presence, andmarketing. The experimental results show that our model
achieves high accuracy. In our future work we plan to analyze
and study social-network dynamics and evolution.
ACKNOWLEDGMENT

P (inco min g = accept | Ti , D j , Locl )=P (Ti , D j , Locl )We would like to thank Nathan Eagle and Massachusetts
Institute of Technology for providing the call logs of theReality Mining dataset.

VI. EXPERIMENTAL RESULTS AND DISCUSSIONSREFERENCES

P (Ti , D j , Locl | inco min g = accept ) P (inco min g = accept )A. Real-life Data Sets and Parameters
Real-life traffic profile: In this paper, actual call logs areused for analysis. These call logs of 81 users were collected
for a period of 8 months at MIT [4] by the Reality Mining
Project group. Additionally, the call logs of 20 users werecollected for a period of 6 months by the Network Security
team at UNT.
The Reality Mining Project group collected data on mobile
phone usage of 81 users, including user ID (unique number
representing a mobile phone user), time of call, call direction(incoming or outgoing), incoming call description (missed or
accepted), talk time, and tower ID (location of phone user).
These 81 phone users were students, professors, and staff
members. The collection of the call logs was followed by asurvey to gather feedback from participating phone users
about behavior patterns such as favorite hangout places;
service providers; talk-time minutes; and phone users’ friends,
relatives and parents. More information about the Reality
Mining Project can be found in [4].
(Because of the limited space we will show theexperimental results in the workshop)
The experimental results show that our approach iseffective.
VII. CONCLUSION[1]

S. Wasserman and K. Faust. Social Network Analysis: Methods andApplications. Cambridge University Press, 1994.
[2] N. Eagle, A. Pentland, and D. Lazer. “Inferring friendship network
structure by using mobile phone data,” in Proceedings of the National
Academy of Sciences. vol. 106, no. 36, pp. 15274-15278, 2009.
[3] M. Fannes and P. Spincemaile. “The mutual affinity of randommeasures”. Periodica Mathematica Hungarica, vol. 47 (1–2), pp. 51–71,
2003.
[4] Massachusetts
InstituteofTechnology:
Reality
Mining.
http://reality.media.mit.edu/ 2009.
[5] L. Katz and J. Powell. “Measurement of the tendency toward
reciprocation of choice,” Sociometry, vol. 18, pp. 659-665, 1955.
[6] J. W. Cangussu, M. Baron. “Automatic identification of change points
for the system testing process,” in Proceedings of the 30th Annual IEEE
International Computer Software and Applications Conference(COMPSAC 2006), Chicago, IL, Sept. 18-21, 2006.
[7] J. W. Harris and H. Stocker, Handbook of Mathematics andComputational Science, New York: Springer-Verlag, 1998, §21.10.4,
p. 824.
[8] N. Nilsson. Artificial Intelligence, a new synthesis, first edition, San
Fransisco: Morgan Kaufmann Publishers, 1998.
[9] A. Pentland, “Collective intelligence,” IEEE Computational Intelligence
Magazine, vol. 1, pp 9-12, 2006.
[10] A. Pentland, “Automatic mapping and modeling of human networks,”
Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 378,
pp. 59-67, 2007.
[11] N. Eagle. "Behavioral inference across cultures: using telephones as acultural lens," IEEE Intelligent Systems, vol. 23, no. 4, pp. 62-64, 2008.
[12] G. E. P. Box and G. M. Jenkins and G. C. Reinsel. Time series analysis:
Forecasting and control, 3rd ed., Prentice-Hall, Englewood Cliffs, NJ,
1994.

In this paper we propose an integrated platform for social
relationship and human behavior analysis based on mobile
phone call detail records. Because of the diversities andcomplexities of human social behavior, one technique cannot
Book of abstracts for NetMob 201024

Session B

Book of abstracts for NetMob 201025

Book of abstracts for NetMob 201026

Timescales in evolving mobile networks
Gautier M. Krings
Université catholique de Louvain

Márton Karsai
Aalto University

Jari Saramäki
Aalto University

Vincent D. Blondel
Université catholique de Louvain
Mobile phone networks have raised a wide interest in
the past years, thanks to the recent availability of large
sets of mobile phone call records (CDRs). Those datasets consist of calls made by users from mobile phone
providers during time periods ranging from a couple ofweeks to several years. They provide interesting advantages compared to other datasets as fixed phone callrecords or emails. First, a mobile phone is a personal
object (in opposition to fixed phones that are usuallyshared between groups of people), this allows to derivea social network directly from the call data records. Secondly, as a call can only involve two persons at thetime, the calls contained in the dataset represent realinteractions between individuals. This is not always thecase, as for email networks, where one email can be sent
to a large number of recipients in a small time.
Moreover, those datasets possess a strong temporalcomponent, as the edges of a mobile phone network
are originated by calls between users. The timestampof a call is particularly interesting as it allows to quantify the strength and the regularity of a relationship.
This is a significant advantage compared to datasets
provided by online social networks, where friendships
are usually defined in a static way.
The availability of such datasets have led to various
analyses of the structure of mobile phone networks,
which followed all a systematic procedure : from thedataset, a digraph is constructed by representing customers as nodes, and drawing an edge between two nodes
if they have made at least one call over the whole period. The edges are then usually weighted, either with
the number of calls, or with the total calling time between the two users. In some cases, some thresholding is
performed to remove outliers from the dataset.
When one uses this approach, the strength of an edge
represents the frequency of interaction between two
users as a fixed value, with the assumption that the frequency of calls is constant over time. When one thinks
about it, the frequency of interaction between two users
should logically be varying over time, but the representation of the network by a static graph hides completely
the dynamics of the edges.
To avoid this, one needs to represent the network as an
evolving graph.
As said earlier, a dataset representing a mobile phone
network is a collection of events ((i, j) , t), meaning that

customer i has called customer j at time t.
When the time resolution is high, only a few events
happen at a single timestep and the graph is composedof sparse edges changing at a high frequency. It is thenhard to make a clear analysis of the dynamical behaviorof such a graph.
The classical approach to eliminate the high-frequency
noise and extract global trends from an evolving graphis the segmentation of the dataset into time windows.
The time interval is sliced into several continuous time
windows, and for each window, one static graph that
contains all the events happening within the window isbuilt.
This approach is similar to a moving average techniquein time series analysis that are used for denoising purposes. It presents also the same issues : if a window is
too small, high frequency noise is not eliminated andhides the general trends. If it is too large, the result isa static network, without dynamical information.
Therefore, a good choice for the length of time windows is crucial, but usually left behind by researchersand motivated by intuition.
In this work, we propose a method to analyze the influence of the length of a time window on the graph it
generates and to characterize the growth of an evolving
graph with time.
We consider the evolving graph as a stochastic process,each possible edge being a variable that appears witha non-stationnar probability. We estimate the quantityof information of a growing set of events and track the
redundancy of the set of events. We use the redundancy
to quantify the graph growth and as stopping criterion
for the graph aggregation.
We apply our method to a mobile phone network of 3
million users making 360 million calls over 6 months,
and show that after 3 weeks, the network growthreaches a steady state that can be expressed matematically. We also analyze similarity measures on the sequence of graphs created by windows of different sizes
to validate 3 weeks as an adequate window length.

Book of abstracts for NetMob 201027

Towards an investigation of the structure and temporal
dynamics in a large scale telecoms dataset
Fergal Reid
Clique Research Cluster
University College Dublin
Dublin 4, Ireland
fergal.reid@gmail.com

1

Neil Hurley
Clique Research Cluster
University College Dublin
Dublin 4, Irelandneil.hurley@ucd.ie

Motivation

Clique (clique.ucd.ie) is a research project started in January 2009, focussing on complex
network analysis and visualization. In conjunction with three industrial partners, Clique isaddressing four core research challenges, namely: the identification of coherent communities,
the identification of nodes that have pivotal roles, the identification of network structure that isremarkable or anomalous and the question of how to model and analyze information flow. Our
research concerns datasets that are massive, multi-attribute and dynamic and is driven by theindustrial contexts provided by our industrial partners.
One of our research domains is very large scale mobile telecoms datasets. These datasets
provide a rich source of human social interaction data and provide an excellent opportunity toinvestigate large scale complex networks. The particular data provided by our industry partner
1
yields call graphs where a single week worth of data contains many millions of nodes, withthe sparse edge structure typical of such networks. Having access to week by week snapshots ofthis rich data, over a period of time spanning many months, we are conducting research to findstructure and regularity in this data, with a view to investigating the underlying social structure
and attempting to discover the channels through which influence propagates in complex and social
graphs. We are specifically considering the problems of finding interesting graph structures - suchas the clusterings of nodes that form communities - and diffusion modeling of user influences inareas such as network churn and handset adoption.

(a)

(b)

Figure 1: The degree distribution of (a) one months worth of raw call data and (b) one months
worth of SMS data. No filtering of high degree nodes, call centers etc has been performed on
this data.
1 We would like to acknowledge Idiro Technologies for providing us with access to this data.

Book of abstracts1for NetMob 2010

28

(a)

(b)

Figure 2: The connected component size distribution of (a) one weeks raw SMS data (b) one
months raw call data. Huge components clearly visible.

2

Completed WorkAs a prerequisite for developing techniques to predict influence diffusion within a social graph,
it is first necessary to investigate the structure and dynamics of the graph. Much work has
been done on community assignment in graph datasets - thoroughly summarized in the review of[Fortunato, 2010]. However, after the analysis of [Leskovec et al., 2008] some question exists overwhether the existing community assignment solutions will successfully operate within the densely
overlapping cores of large social graphs, and effectively extract useful community structure. It
is against this backdrop that we attempt to find structure in our data.
As a first step, we attempt to characterize our data in terms of several metrics that havepreviously proven useful in the study of complex networks. The degree distribution of static
graphs extracted from a month long time period is shown in Figure 1, where we separately
examine call and SMS data. Note that the degree distribution of the both networks, when viewed
as an undirected, unweighted graph, exhibits the heavy tail properties previously described in
the work of [Onnela et al., 2007] and [Dasgupta et al., 2008]. In Figure 2, the distribution ofconnected component sizes of a weeks worth of SMS data, and a months worth of call data isshown. Again, in agreement with the findings of [Onnela et al., 2007],[Dasgupta et al., 2008] thevast majority of nodes are part of a huge connected component. This result holds true in SMS
and call graphs, and even when we consider graphs covering time periods as short as one week.
In reality, the edges in the call graph have multiple attributes, including call type, total callduration and total number of calls, accumulated over the extracted time-period. In Figure 3,
the distribution of edges weighs is plotted, where the edges are weighted according to firstly the
total number of seconds two nodes spend calling each other, and secondly the total number of
SMSs two nodes send to each other.
Having conducted some simple characterization, we have attempted to replicate the experiments of [Onnela et al., 2007], which investigate the ‘weak tie hypothesis’ of [Granovetter, 1973].
Our initial results indicate that our dataset, whether we view a weeks worth of data at a time,or consider longer time periods, such as month by month, also displays the property that theties that are most important for network connectivity are those with smaller dyadic edge weight.
Our work indicates that this analysis holds regardless of whether we weight edges according
to the number of calls sent and received, or by call duration, or by number of SMS messages
exchanged. These initial results are part of an on-going analysis and we expect that structuralcharacteristics such as this will have an important impact on the development of a good modelof influence diffusion.
Investigating correlations between different graph statistics is also important in order toobtain a useful characterization of the data. Currently, we are investigating whether relationships
exist between the degree of a node and the summed weight of its edges, whether there is assortivity[Newman, 2002] between high degree nodes in our dataset, and to what extent the SMS and callgraphs are similar to, or different from, each other. A further area of research is an attempt toclassify nodes by the proportion of communications that they emit and receive, and to study theBook of abstracts2for NetMob 2010

29

(a)

(b)

Figure 3: The edge weight distribution of (a) one months worth of raw SMS data (b) one months
worth of raw call data.
dynamics of changing calling patterns across nodes with different local structural properties.
Edge significance State-of-the-art research has attempted to filter the more ‘casual’ edges froma mobile telecoms network in order to eliminate noise from the social graph, and also decrease
the computational complexity of processing such large networks. For instance, reciprocatedcommunications are used in [Lambiotte et al., 2008][Dasgupta et al., 2008] as evidence of moremeaningful social connection. With similar motivations, and believing network dynamics aninteresting area of investigation, we are attempt to characterize the dynamic properties of edges,
such as the distribution of the length of time an edge that appears in the graph persists for, andcorrelating this with other edge properties such as call duration, bidirectionality, and number ofcalls.
Influence diffusion In addition to anonymised summary call data records, we also have accessto data describing which network users churned from the network at certain times. We also
have information on the handset currently used by each user. One of our ongoing goals is toinvestigate whether we can find a significant social dimension to the spread of changes in handset
adoption, and network churn, after [Dasgupta et al., 2008], as a tool of investigating the social
properties of the spread of influence.

3

Outlook

We intend to proceed along this line of investigation, attempting to find structure in the thesocial network we approximate with mobile call graphs. We are investigating whether welldefined structure can be found in such large networks. We are also investigating the impact ofsocial effects on influence change, specifically on churn and handset uptake. We are scientificallyinterested in whether we can develop a generic way of investigating influence spread that can
extend across mobile datasets and to other complex network domains, and whether we canleverage the dynamic nature of the graph across time to make better models and find richer
structure than we could with a single time slice.
We hope to present some results on this ongoing work by the time of the workshop.

Book of abstracts3for NetMob 201030

References
K. Dasgupta, R. Singh, B. Viswanathan, D. Chakraborty, S. Mukherjea, A.A. Nanavati, and
A. Joshi. Social ties and their relevance to churn in mobile telecom networks. In Proceedingsof the 11th international conference on Extending database technology: Advances in databasetechnology, pages 668–677. ACM, 2008.
Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75 – 174, 2010.
ISSN 0370-1573. doi: DOI:10.1016/j.physrep.2009.11.002.
M.S. Granovetter. The strength of weak ties. American journal of sociology, 78(6):1360, 1973.
R. Lambiotte, V.D. Blondel, C. de Kerchove, E. Huens, C. Prieur, Z. Smoreda, andP. Van Dooren. Geographical dispersal of mobile communication networks. Physica A: Statistical Mechanics and its Applications, 387(21):5317–5325, 2008.
J. Leskovec, K.J. Lang, A. Dasgupta, and M.W. Mahoney. Statistical properties of community
structure in large social and information networks. 2008.
MEJ Newman. Assortative mixing in networks. Physical Review Letters, 89(20):208701, 2002.
J.P. Onnela, J. Saramaki, J. Hyvonen, G. Szabó, D. Lazer, K. Kaski, J. Kertész, and A.L.
Barabási. Structure and tie strengths in mobile communication networks. Proceedings of the
National Academy of Sciences, 104(18):7332, 2007.

Book of abstracts4for NetMob 201031

Dynamics and temporal correlations in mobile phone based social networks
Márton Karsai∗ ,1 Lauri Kovanen† ,1 Mikko Kivelä‡ ,1 Raj Kumar Pan§ ,1 JariSaramäki] ,1 János Kertész∗∗ ,2, 1 Albert-László Barabási†† ,3, 4 and Kimmo Kaski‡‡1
1
2

BECS, School of Science and Technology, Aalto University, Helsinki, Finland

Institute of Physics, Budapest University of Technology and Economics, Budapest, Hungary
3
4

CCNR, Northeastern University, Boston, MA, USA

CCSB, Dana-Farber Cancer Institute, Boston, MA , USA

Complex networks are rarely static, but involve dynamics on several time scales. Often, thenetworks studied in the literature represent either static ”snapshots” of dynamic entities or aggregates over some period of time. In the first case, all dynamics are entirely lost, while in the secondcase some trace of dynamics can be retained e.g. by representing edge activation frequencies asedge weights. However, in this case, all information on short-term temporal correlations between
dynamics of edges is lost.
Here, we study the microdynamics of a large social network reconstructed from mobile communication billing records with time stamps for each communication event (calls and text messages).
It is natural to assume that such events are temporally correlated i.e. incoming calls trigger outgoing calls as some information is relayed, and call patterns of social groups contain temporalcorrelations as messages are exchanged between group members in a conversation.
We begin with the smallest scale interactions, showing that there is clear evidence of correlations
where incoming calls trigger outgoing calls, and discuss the associated time scales. Then we moveon to multipoint correlations by showing that ”temporal motifs” exist within short time windows
in significantly greater numbers than in a temporally uncorrelated reference system. Having shown
the existence of correlations, we assess their significance in the function of a social system in termsof information transmission. We show that unexpectedly, temporal correlations appear to slow
down the transmission dynamics compared to a null reference.

emails:∗ mkarsai@lce.hut.fi] jsaramak@cc.hut.fi† lkovanen@lce.hut.fi∗∗ kertesz@phy.bme.hu‡ mtkivela@cc.hut.fi†† alb@neu.edu§ rajkp@lce.hut.fi‡‡ Kimmo.Kaski@hut.fi

Book of abstracts for NetMob 201032

Communication Motifs: A Novel Approach toCharacterize Mobile Communications
Qiankun Zhao

Nuria Oliver

Telefonica Research and Development, Spainzhao@tid.es

Abstract: Social networks mediate not only the relations between entities, but also the patterns of information
propagation among them and their communication behavior. In this paper, we extensively study the temporal annotations (e.g., time stamps and duration) of historical communications in mobile phone networks and propose twonovel tools for – qualitative and quantitative – characterizations of the patterns of information propagation in these
networks. Specifically, we define communication motifs
and maximum-flow communication motifs in a mobile network as structures that satisfy certain communication andtopological constraints. We propose two motif discovery
algorithms and apply them to the mobile phone network.
Using the discovered motifs to characterize the communication behavior and information propagation patterns
in the mobile networks, we verify the following hypothesis: 1) the functional behavioral patterns of information
propagation within mobile networks are stable over time;2) the patterns of information propagation in mobile networks seem to be sensitive to the cost of communication;and 3) the speed and the amount of information that is
propagated through a mobile network are correlated anddependent on individual profiles.
Summary: Social networks represent the links between
a set of entities connected to each other with different
types of relationships. For example, papers are linked bycitations in a citation network, bloggers are linked by comments or blogrolls in a blog network, while cell phones areconnected via phone calls in a cell phone network [8, 11,1]. In the literature, social networks have been extensively
studied from a graph theory perspective (e.g., power laws,
small worlds phenomenon, coverage, etc.) [3, 6, 2]. Properties of different types of complex networks have been
compared [9, 11, 3]. Recently, research studies on social
networks from a behavioral perspective have received a
lot of attention. These works, dealing with problems suchas community identification, spam detection, or modeling information flows [8, 4] have a lot of applications inrecommender systems, social search, economics, and advertising [12, 5, 7].

nuria@tid.es

In this paper, we study the communication characteristics (from a behavioral perspective) within mobile phone
networks. In particular, we aim at identifying topological subgraph structures with frequency and temporal constraints, which we refer to as motifs, to characterize communications in mobile networks.
caller
2
3
4
3
3
7
7
8

callee
3
4
3
7
8
4
2
4

timestamp
9:00 am, 11-Aug-08
9:10 am, 11-Aug-08
9:41 am, 11-Aug-08
9:51 am, 11-Aug-08
10:36 am, 15-Aug-08
10:08 am, 11-Aug-08
10:43 am, 13-Aug-08
9:36 pm, 15-Aug-08

duration
2 minutes
5 minutes
3 minutes
2 minutes
6 minutes
6 minutes
6 minutes
6 minutes

Table 1: CDR(Call Detail Records) data
A fundamental issue in analyzing information flow or
propagation patterns within communication oriented social networks is how to represent the communication datain such a way that it captures every piece of useful information. Consider the example in Table 1, which shows eight
entries from a phone call detail record (CDR) dataset,
where calls between users and their associated durations
and timestamps are recorded, with one entry per call. A
number of alternative representations of the CDR data in
Table 1 are shown in Figure 1. Here G1 is constructed bytaking each user as a node and each call between any two
users as an edge between the two corresponding nodes,
while G2 extends G1 by adding weights to the edges proportional to the frequency of calls between any two nodes)
and G3 is obtained by removing the direction of the edges
in G1 .
1

8

8
2

7

1

1

8

3

6

4

5

G1

2

2

7

3

6

4

5

G2

7

3

6

4

5

G3

Figure 1: Graph Representations of CDR data.

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$10.00.

These representations are meaningful and valid in certain social networks such as friends or citation networks,
where the nature of the relationship is embedded in – ormay be easily derived from – the records. However, inthe case of social networks derived from communication
logs, it is difficult to properly infer the nature of the relationships due to the multiplicity of reasons for making aBook of abstracts for NetMob 201033

call (e.g., business, personal, service, etc.) and the importance of the temporal context. In other words, once one
paper cited another, the cited relationship between both
papers always holds true. However, phone calls are madefor different reasons and hence the nature of a relationshipbetween two nodes in the network may also depend on thetemporal context of calls, i.e., a call made during working hours is probably of different nature than a call madeat night. The same applies to other temporal attributes
such as duration and frequency of the interaction, or temporal distance between two calls (inter-call time delay).
As a result, the representations that are used in existing
information propagation studies are not valid under thecontext of our study in this paper. Furthermore, manystudies on information propagation assume that consecutive interactions transmit the same piece of information
within the inferred networks, and we shall argue that thisassumption is not always valid.
In [6], Kleinberg et al. notice the importance of the temporal annotation in instances of communications. Theyfind an information pathway where users are updated withthe latest information at the quickest speed based on thetemporal distance between the communications. However,their work does not consider the case of different pieces of
information being propagated in the same network. Moreover, by using part of the temporal information only, they
are not able to generalize the local behavior patterns ofindividuals or small groups to the entire network.
In this paper, we propose to study information propagation and behavior patterns in communication orientedsocial networks, taking a mobile phone network as an example, by leveraging the temporal annotations of thesecommunications together with the topological structure of
the network. The proposed approach is based on the following observations:• Calls or interactions between the same two users in
the network may have different purposes and thustransmit different information, causing different effects in terms of information propagation. The interactions between any two users may range frombeing intense and frequent to being isolated events
without further impact on the network. As a result,
we propose to differentiate the calls by incorporating
the temporal information of the calls into the social
networks.
• The semantics associated with each interaction (e.g.,
topics discussed, purpose of a call) are hard to infer [9, 11, 3]. It is possible that two adjacent interactions (i.e, interactions that share at least one
common user) have no causal relationship between
them. However, the temporal attributes associatedwith the interactions may shed some light on theamount of information propagated. For example, it
seems reasonable to assume that the closer in time
two adjacent interactions take place, the more likely
it is that they are about the same topic.
• The amount of information passed from one nodeto another in the social network may be quantified
in different ways. For example, in a CDR dataset
the amount of information can be quantified by the
duration of the call, whereas in a Facebook dataset
the amount of information can be quantified by thelength of the text typed on a user’s wall. In bothcases, we assume that the longer an interaction is,
the larger amount of information is propagated via
this interaction.
1

8

2

1
2

2

8

2

8

3

7

2
3

3

6

3

4

5

4

g1

7

3

7

g2

4

4

g3

g4

5

4

g5

Figure 2: Representation with temporal constraint.
Based on the above observations, we aim to find noveland meaningful ways to model the users’ behaviors and information flow patterns. For example, based on the CDR
data in Table 1, five different calling sequences are constructed by taking the call timestamps into account asshown in Figure 2. In these graphs, two edges are connected if and only if their corresponding timestamps arewithin 30 minutes of each other. Compared to the graphs
in Figure 1, the five sequences in Figure 2 take into account the temporal information of the calls.
In order to model how information is propagated withina mobile phone network, we propose the concepts of communication motifs and maximum-flow motifs. The proposed motif concepts are an extension of the network motifs in biological networks [10], which refer to patterns
that recur within a network much more often than at random. We propose two efficient algorithms to automatically identify communication motifs in a network, carryout extensive experiments with a large mobile phone network dataset and discuss the properties exhibited by thediscovered motifs. Finally, we characterize the information propagation behavior in the mobile phone network
using these motifs as a measurement, which leads us to
the following findings:• The functional behavioral patterns of information
propagation are stable over time;• The patterns of information propagation are sensitive to the cost of communication;• The amount of information being propagated and its
speed are correlated and depend on user profiles in
the mobile phone network.
As supported by our research results, we shall claim thatthe temporal attributes associated with communication
data are critical to model information propagation andcharacterize the nature of the relationship between any
two nodes in the network. In future work, we plan tocontinue this line of research.

1. REFERENCES[1] A. Anagnostopoulos, R. Kumar, and M. Mahdian.
Influence and correlation in social networks. In ACM
SIGKDD, pages 7–15, 2008.
[2] W. Chen, Y. Wang, and S. Yang. Efficient influencemaximization in social networks. In ACM SIGKDD,
pages 199–208, 2009.
[3] N. Du, C. Faloutsos, B. Wang, and L. Akoglu. Large
human communication networks: patterns and autility-driven generator. In KDD ’09, 2009.

Book of abstracts for NetMob 201034

[4] L. Guo, E. Tan, S. Chen, X. Zhang, and Y. E. Zhao.
Analyzing patterns of user content generation in
online social networks. In ACM SIGKDD, pages
369–378, 2009.
[5] A. Gürsel and S. Sen. Producing timely
recommendations from social networks throughtargeted search. In AAMAS, 2009.
[6] G. Kossinets, J. M. Kleinberg, and D. J. Watts. The
structure of information pathways in a social
communication network. In KDD, 2008.
[7] T. Lappas, K. Liu, and E. Terzi. Finding a team ofexperts in social networks. In ACM SIGKDD, pages
467–476, 2009.
[8] Y.-R. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. L.
Tseng. Facetnet: a framework for analyzing
communities and their evolutions in dynamic
networks. In WWW, 2008.
[9] R. MIlo, S. Itzkovitz, N. Kashtan, R. Levitt,
S. Shen-Orr, I. Ayzenshtat, M. Sheffer, and U. Alon.
Superfamilies of evolved and designed networks.
Science, 303(5):1538–1542, March 2003.
[10] R. MIlo, S. Shen-Orr, S. Itzkovitz, N. Kashtan,
D. Chklovskii, and U. Alon. Network motifs: Simple
building blocks of complex networks. Science,
298(25):824–827, October 2002.
[11] J.-P. Onnela, J. Sarama, J. Hyvonen, G. Szabo,
D. Lazer, K. Kaski, J. Kertesz, and A.-L. Barabasi.
Structure and tie strengths in mobile communication
networks. PNAS, 104(18):7332–7336, May 2007.
[12] P. Raghavan. The changing face of web search:algorithms, auctions and advertising. In STOC,
2006.

Book of abstracts for NetMob 201035

Mobility, Data Mining and Privacy: The GeoPKDD Paradigm
Fosca Giannotti
KDD Lab - ISTI - CNR
Pisa, Italy

Fabio Pinelli
KDD Lab - ISTI - CNR
Pisa, Italy

Salvatore Rinzivillo
KDD Lab - ISTI - CNR
Pisa, Italy

Roberto Trasarti
KDD Lab - ISTI - CNR
Pisa, Italy
March 4, 2010
Abstract
The technologies of mobile communications and ubiquitous
computing pervade our society, and wireless networks sense
the movement of people and vehicles, generating large volumes of mobility data. Miniaturization, wearability, pervasiveness are producing traces of our mobile activity, withincreasing positioning accuracy and semantic richness: location data from mobile phones (GSM cell positions), GPStracks from mobile devices receiving geo-positions fromsatellites, etc. This paper gives a short overview of the analytical tools developed within the European Project GeoPKDD (Geographic Privacy-aware Knowledge Discovery and
Delivery), a project funded by European Commission under
the FET program of the IST FP6 framework.

Figure 1: The GeoPKDD process

1 Introduction
Research on moving-object data analysis has been recently
fostered by the widespread diffusion of new techniquesand systems for monitoring, collecting and storing location
aware data, generated by a wealth of technological infrastructures, such as GPS positioning and wireless networks.
These have made available massive repositories of spatiotemporal data recording human mobile activities, that callfor suitable analytical methods, capable of enabling the development of innovative, location-aware applications. The
GeoPKDD project [1], since 2005, investigates how to discover useful knowledge about human movement behavior
from mobility data, while preserving the privacy of thepeople under observation. GeoPKDD aims at improving
decision-making in many mobility-related tasks, especiallyin metropolitan areas.
The GeoPKDD system, originally presented in [5], allows to handle the whole knowledge discovery process frommobility data, in particular it provides tools for reconstructing a trajectory from raw logs, storing and querying trajectory data, classifying trajectories according to means oftransportation (pedestrian, private vehicle, public transportation vehicle, extracting spatio-temporal pattern and models
as useful abstractions of mobility data, find an optimal tradeoff between privacy protection and quality of the analysis.

2 Experimenting on real GSM data
To demonstrate the power of our framework we have tested
it on different real scenarios and different data sources. Here
we present a set of experiments on a dataset of real GSM
data logs. The observations are collected by the Telecom
Italia Lab, the research laboratory of the main telecommunication company in Italy, using an estimation of the positionof the devices by means of triangulation. The dataset contains the points recorded along a whole day (in particular the
21st May, 2009). The first step was the importing of the observations in the data management system which is based on
Oracle 11g database. The trajectories are built starting fromthis raw data using the trajectory reconstruction algorithm,
and cleaning them from errors and outliers obtaining a set ofdata2010(Fig.2).
Book of abstracts usefulfor NetMob36
1

2
Fig.4.

Figure 2: The reconstructed moving points dataset
Figure 4: The density distribution plot (Left) and the density
distribution on the grid (Right)
The resulting set is composed by more than four million
trajectories in the urban area of Rome.
2.1 Statistical Analysis. A set of statistical analysis can beeasily computed having the data storage system integrated
with a set of spatio-temporal primitives, that allow to efficiently compute spatial and temporal measures, like temporal gaps and spatial distances between consecutive points.

Using the temporal dimension we can focus the view
only in a specific period, say from 6 am to 12 am, obtaining
the Fig.5. As we can see in the morning the mobility isgreater between two dense points in the south part of the city
giving to the mobility manager the idea of where the peek ofdetected in the first analysis is focused.

2.1.1 Distribution of movements during the day. For thisanalysis we partition the day in hours (0-24) and we willintersect the trajectory dataset with this periods counting thepresence of the trajectories in them. The result is shown in
Fig.3.

Figure 5: The density distribution in the morningof movements

Figure 3: The Time distribution of movements

To better understand the traffic flows of the traffic weproceed with the next statistical analysis called O-D Matrix.

2.1.3 O-D Matrix. Usually this analysis is obtained by
the mobility agencies using a survey obtained from direct
or by telephonic interview to the citizens. The quality ofthe data obtained in this way is very poor and has very highcosts. Instead thanks to our system this can be done witha very low cost and high precision avoiding incomplete andincorrect data. For this example we introduce a bigger grid
20 × 20 which simulates the districts of the city. Having
2.1.2 Density of movements in space. The distribution more information like real districts or regions of interestof movements can be analyzed not only in time but also in given by the mobility agency we can use them to performspace. For example, by dividing the territory in a grid of this analysis. Joining the matrix with the used grid we can
50 × 50 cells, we can compute the density within each cell. browse it by selecting a region as origin or destination. In
In this case we can take advantage from the previous analysis Fig.6 we show how the people move from and to a cells.
obtaining a spatio-temporal density distribution which can be
The next section will show a further step: the statisticalnavigated in both dimensions. The global
resultis shown
analysisBookof abstracts
for in
NetMob2010 using data mining algorithms such as T-Clustering
37
The analysis shows two major peeks during the day
corresponding to the periods of time where the people aregoing or coming from work. Another aspect of the mobility
is highlighted: the period between the peeks has a very highnumber of movements which gives to the mobility agent aclue about the sustainability of the traffic during such hours.

3

Figure 6: The OD Matrix focused on the yellow cell. The
destinations (Left) and the origins (Right)[3] and T-Pattern [2] and how they can interact with theprevious analysis thanks to the unifying system.
2.2 Data mining analysis. The understanding of themobility in a city is a very complex process, here we
present an example of how the presented framework helps
the analyst in the discovery process. An example of analysis
is looking for common behavior of people who move toward
a common destination. To perform this task the first stepis to find this communities of people: the Fig.7 shows
two clusters obtained applying the T-Clustering using thecommon destination distance function. Once the analyst
identifies the clusters of intersect, it is possible to refine theanalysis by investigating other regularities in their behavior,for example by applying the T-Pattern algorithm on the
trajectories of one of the selected cluster (say, for example,
the red cluster in Fig.7). The resulting T-Patterns are shownin Fig.8.

Figure 7: Two Clusters discovered using common destination distance function

Figure 8: The T-Patterns discovered on the trajectories in aclusteralgorithms obtaining a deep understanding of the data.
The approach of combining the extracted patterns with
the information available in the system can be also exploited
to learn another type of model: the Location Prediction[4]. The location prediction algorithm aggregate the local
patterns found in the previous step to produce a global
model for the considered dataset: the model gives a highlevel description of the mobility allowing also to predict thepossible destinations of an individual by observing his/her
movements in the recent past.
3 Conclusions
The analysis capabilities of our system have been applied
onto a massive real life GSM dataset and we demonstrated
how the various methods and systems developed in the
project support the creation of novel analytical services formobility management, such as: i)Analysis of the movements in space and time ii) the automated construction of origin/destination matrices from mobility data in a timely, reliable and objective manner. It allows to analyze users’s flows
between geographical areas, overcoming the limitations of
the current survey-based approach; iii) discovery of mobility
patterns with different data mining tools which can be combined to go deep on the data understanding iv) the detailed
analysis and discovery of systematic movement behaviors,
i.e., the movements that repeat periodically during the week,with particular emphasis to commuting patterns like hometo-work and work-to-home.

To give semantic to the T-patterns extracted we canintersect the regions of the T-Patterns with a set of interesting
places (specified by the mobility agency), and discover that
the T-Pattern in Fig.8(b) represents the behavior of people
coming in a common area. This simple process show
the capabilities of the system allowing the user to perform References
iterative querying mixing together different Book
dataofmining
abstracts for NetMob 201038

4[1] Geographic Privacy-aware Knowledge Discovery and Delivery Project. GeoPKDD, http://www.geopkdd.eu/[2] F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining. In KDD, pages 330-339, 2007.
[3] G.Andrienko, N. Andrienko, S. Rinzivillo, M. Nanni and
Dino Pedreschi. A Visual Analytics Toolkit for Cluster-BasedClassification of Mobility Data. SSTD, pag. 432-435(2009)[4] Anna Monreale, Fabio Pinelli, Roberto Trasarti, Fosca Giannotti: WhereNext: a Location Predictor on Trajectory Pattern Mining.KDD 2009. 15th ACM SIGKDD Conference on
Knoledge Discovery and Data Mining[5] Riccardo Ortale, E. Ritacco, Nikos Pelekis, Roberto Trasarti,
Gianni Costa, Fosca Giannotti, Giuseppe Manco, Chiara
Renso, Yannis Theodoridis: The DAEDALUS Framework:
Progressive Querying and Mining of Movement Data. ACM
SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008).

Book of abstracts for NetMob 201039

Book of abstracts for NetMob 201040

Session C

Book of abstracts for NetMob 201041

Book of abstracts for NetMob 201042

Authors: Pu Wang, Marta C. González, Ronaldo Menezes and Albert-László Barabási
Affiliations:
P. Wang is with the Center for Complex Network Research, Northeastern University, Boston,
Massachusetts, USA and the Department of Physics, University of Notre Dame, Notre Dame, Indiana,
USA
M. González is with the Department of Civil and Environmental Engineering, Massachusetts Institute ofTechnology, Cambridge, Massachusetts, USA
R. Menezes is with the Department of Computer Sciences, Florida Institute of Technology, Melbourne,
Florida, USA
A.-L. Barabási is with the Center for Complex Network Research, Northeastern University, Boston,
Massachusetts, USA and the Department of Medicine, Harvard Medical School, Harvard University,
Cambridge, Massachusetts, USA
Emails:pwang2@nd.edu
marta.gonzalez.v@gmail.com
rmenezes@cs.fit.edu
barabasi@gmail.com
Abstract:
The history of technological viruses is intrinsically linked to the history of computational devices. Since
the inception of the Internet, programmers begun writing self-replicating executables such as Creeper,
the first known instance of a computer virus. From there on, the field of computer security grew
together with the ability of programmers to write increasingly more sophisticated viruses. In recent
years mobile phone devices have become the new frontier for self-replicating programs. The availabilityof these devices together with its constant online presence makes them an ideal breeding environment
for technological viruses. Yet, society has not been affected by major mobile virus outbreaks. A natural
question then becomes: Why are desktop and laptop computers so vulnerable to a problem that mobile
phones do not seem to be? This paper shows that the spread of mobile phone viruses is limited by thetype of viral behavior (topological or scanning), the existence of a market share providing sufficienthomogeneity in the world of devices, and the mobility of individuals. We find that hybrid mobile viruses
that include some level of random scanning have a higher chance to bring havoc to the mobile
community than their standard topological counterparts even under adverse conditions to the virus,
such as protection mechanisms used by phone providers.

Book of abstracts for NetMob 201043

Human movements and the spread of infectious
diseases
Vitaly Belik1 , Theo Geisel1 and Dirk Brockmann2
1 Max-Planck-Institute for Dynamics andSelf-Organization, Göttingen, Germany

tle against them. In the past mathematical epidemiology approached this problem relying on rare
empirical data and posteriorly predictions. Nowadays availability of large amount of data on human activity, in particular its mobility patterns, allows us to approach an ultimate goal of forecasting the progress of an epidemic and planning response measures on the fly. We already experienced
such kind of forecasting during the recent outbreakof H1N1 influenza pandemic [1, 2]. However, thedetailed computational platforms simulating epidemic spread could be used in non-ambiguous way
only if one fully understands the driving factors andessential constituents of a model. This requires athorough theoretical investigation of the underlying
epidemiological model. To this end in the present
contribution we address the role of human mobilityon the spread of infectious diseases.

2 Northwestern University, Evanston, IL, USA

Abstract
Modern technologies allow collection and processing ofan abundance of information on human activity, in particular, its mobility patterns. This opens unprecedented
opportunities for development of computational models
of many human-mediated phenomena such as the spreadof infectious diseases. The main modeling approach for
spatial epidemics explicitly incorporating traveling behavior of the host is the reaction-diffusion model. It assumes random, markovian movements of the host. Thisapproach seems to be inappropriate for humans that typically return to their home locations after traveling. We
investigate a model explicitly incorporating bidirectional
human movements on star-like network topologies consisting of central home nodes and distant locations. We
show for various topologies that dependent on parametersboth models exhibit strong differences as well as similarities. An important result is the attenuation of epidemics
in bidirectional systems as compared to generic reactiondiffusion systems. Global outbreak of an epidemic is determined by a threshold value of the characteristic timespent by an individual on distant locations. Our results
provide a framework for incorporating an abundant dataon human mobility available today.

Recent empirical studies on human mobility revealed complex although universal dynamical features of human movements. The laws governing
human mobility include anomalous diffusion [3]and high degree of predictability [4, 5]. An important property of human mobility is their tendency
to return to a few most preferred locations such ashome and workplace. This empirical evidence lead
us to devising an epidemiological model, explicitly
incorporating the last property.

A major theoretical framework for modeling the
spread of infectious diseases explicitly taking into
account host movements is the reaction-diffusion
approach. This approach assumes that hosts areindistinguishable and move randomly between all
available locations like chemical particles. How1 Introduction
ever recent empirical findings suggest a high degree
Infectious diseases remains a pressing challenge for of regularity and predictability in human movehumankind. Understanding the dynamics of epi- ments and thus the reaction-diffusion approachdemics would significantly contribute to the bat- is not appropriate for description of human epi1

Book of abstracts for NetMob 201044

demics.
In what follows we introduce a model explicm
Fnm
itly incorporating human travel into epidemiologn
ical framework. We show for various topologiesmthat there can be a significant difference in thenbehaviour of reaction-diffusion and bidirectional
Fnm
Fnm
models. We discovered a novel kind of a threshold behaviour of an epidemic outbreak dependingon the dwelling time of individuals on distant locations. We show that even in the parameter range
Fig. 1: Illustration of the approach used towhere the global outbreak occurs, there is still aparametrize the bidirectional model. Largepronounced differences in the speed of propagation
circles represent two locations populatedof both kinds of epidemics.
by different species (red and blue). Color
arrows correspond to fluxes of different
2 Modelspecies. On the right a transection of thetotal flux Fnm between locations is shownn (blue) andWe consider an epidemiological model explicitly
consisting of sub-fluxes Fnmmincorporating movements of hosts distinguishable
Fnm (red).
according to their location of origin [6]. If Xnm denotes the number of individuals originating fromn , which delocation m and sojourning in location n. Then the ify any conditions on travel rates ωkm
traveling between different locations is described fine how and along which links in a mobility network individuals travel. In the following we reby the following scheme
strict our-self to the case of traveling on overlapωn
m km kXn !
Xn ,(1) ping star like topologies [8, 9], where nodes reprenωmksent a center of a star and links to the next neighbors in a network of locations represent rays ofn and ω n are forward and backward
where ωkm
the star. Individuals of one particular location canmktravel rates. Note, that considering all individu- travel only on the corresponding star. If they visit
als indistinguishable we get rid of n-dependence of one neighbor location, they need to return home,n ≡ωtravel rates ωkm
km ∀ n and recover random walk before visiting another neighbor location. Matheor diffusive travel.
matically we can describe this by choosing travel
We chose an SIR epidemiological model [7] to rates as ω n = ω n δkn + ω n δmn . We will call thisnm
km
kn
model the local infectious dynamics, which subdi- model bidirectional because individuals travel forthvide individuals into classes according to their in- and back between locations always returning home
fectious status. These include infecteds Inm , suscep- before traveling further in contrast to erratic usutibles Snm which can catch a disease, and recovereds ally not returning random walk travel of reactionRmn denoting either immune or dead individuals de- diffusion model. This setup is a good approximapending on which disease is modeled. Then the lo- tion to describe movements of humans, in particucal epidemic is described by the following scheme lar, commuting behaviour.
k
Ink + SmInkα

Ink + Imk

β

Rkn ,

→
→

(2)

2.1

Parametrization

In order to investigate bidirectional model and compare it with widely used reaction-diffusion model,
we need to use conventions concerning the parameters of the model and underlying mobility network. As an artificial mobility network we will
use a regular one-dimensional lattice and uncorre-

where α and β denotes infection and recovery
rates. Combined, (1) and (2) define our model.
We assume that individuals in locations are well
mixed and one can apply standard chemical kinetics rules. Note, that up to now we did not spec2

Book of abstracts for NetMob 201045

lated scale-free network [10, 11]. We also considered other random networks (Erdős-Rényi, WattsStrogatz), which we do not discuss, but the major
results are independent of particular topology andare present in all of them.

1
0.9

After numerically generating a particular topology, we assign to every node a nominal population
size Nn , chosen randomly from a uniform distribution. In order to compare epidemiological models explicitly incorporating travel, i.e. bidirectionalmodel and reaction-diffusion model, we calibrate
both system in a way, that the total fluxes of travelers between locations are kept the same in both
systems. Being aware only of the total fluxes between locations it is impossible to distinguish between bidirectional and reaction-diffusion travelingmechanisms. Further convention is a constant ren ≡ ω $ corresponding to equal
turn travel rate ωnm
dwelling times on distant locations independent
from the location of origin. However the knowledge of only total fluxes between locations is notenough to extract travel rates of bidirectional model
as it becomes clear from Fig. 1. You see there,that the total flux Fnm from location m to location
m of individuals orign consists of partial flux Fnm
inating from location m and traveling to location
m of individuals origin as well as partial flux Fnm
nating in location n, having dwelled in location m
and returning to location n. We solve this dilemma,
by proposing a vein model which states that partial fluxes are proportional to the sizes of different
n = F N /(N + N ). Uslocal populations:. Fnm
nm nnm
ing the last expression, conservation of individuals
originating from a particular location, and detailedbalance conditions on travel rates we derived a system of linear equations which uniquely maps total
fluxes onto travel rates$ωnm +

0.7

200

0.6

150

0.5

Peak time, τAttack ratio, ρ

0.8

100

0.4

50

0.3

0
1
10

2

3

4

10
10
Return rate, ω−

0.2

10

0.1
0 1
10

2

10

3

4

10
10
Return rate, ω−

5

10

6

10

Fig. 2: Attack ratio % in dependence on return
rate ω $ for a fixed value of total averaged
flux rate %ω& = 1 for a SIR epidemic ona scale-free network with power-law exponent & = 1.5 and with 1000 nodes populated uniformly with %N& = 250 individuals each. Inset shows the dependence ofpeak time ' on return rate ω $ for bidirectional epidemic (circles) and reactiondiffusion model (dashed line). Results wereaveraged over 50 stochastic realisations. Infection rate α = 1, recovery rate β = 0.1.
the number of individuals pro location
ω+ =

ω $ω
,
2(ω $ $ ω)

where from follows ω $ > ω which is a constrain of
constant total flux rate ω. To assign total fluxes in
an inhomogeneously populated complex networkof location we use an ansatz Fnm ' Nn Nm reminiscent of gravity law [12].

ωkm
Fnm
Fnm
Akm $ = $.
Nn + Nm ∑ω
Nn + Nmk

3

Results

Most important questions which could be answeredby an epidemiological modeling are under which
conditions an epidemic outbreak occurs and how
fast it spreads. The conditions under which an epidemic outbreak occurs are usually given by threshold parameters. The most important threshold parameter in epidemiology is a basic reproduction
number R0 , giving a number of newly infected in-

Numerical solutions of the last equation reveals alower boundary for the return rate. We could explain the existence of such a boundary by considering a simple one dimensional homogeneous lattice topology, where we can easily obtain relation
between forward travel rate ω + and random walktraveling rate ω being the total flux normalized by
3

Book of abstracts for NetMob 201046

dividuals in a fully susceptible population causedby one infected [7]. For SIR model R0 = α/β . If
R0 > 1 there is an epidemic outbreak, otherwise— no outbreak. In the context of reaction-diffusion
SIR epidemic model, the concept of global invasion threshold was recently introduced [13]. This
global invasion threshold is determined by a minimal flux between locations in order for epidemic
to affect the majority of locations. We discovered a
new invasion threshold in a bidirectional SIR model
which is determined by the return rate ω $ or by thetime an individual spends on distant locations. The
existence of this threshold is evident from Fig. 2
where the dependence of the attack ratio % on the
return travel rates ω $ for a bidirectional SIR epidemic on a uncorrelated scale-free network [11] ispresented. Attack ratio % gives a fraction of theoverall population affected during an epidemic. We
fixed total flux at a value sufficient for a global outbreak in a reaction-diffusion system. As one observes for low return rates the attack ratio is close
to unity as it is expected for given parameters α
and β thus witnessing a global outbreak. However,with growing values of the return rate, the attack
ratio drops almost to zero reflecting the absenceof the global outbreak. The regime of high return
rates corresponds to small dwelling time on distant locations and thus an infected has not enoughtime to transfer an infection to susceptibles in unaffected locations before returning home. Thus wecan define a threshold value of the return rate determining with a high probability the existence of the$
global outbreak (in Fig. 2 ωthreshold( 103 $ 104 ).
If we consider the dynamics under the threshold,where the global outbreak occurs, there are still
significant differences in the behaviour of bidirectional and reaction-diffusion models. In the inset
of Fig.
the dependence of a peak time
´ 2 we present´' = I(t)tdt/ I(t)dt or a time from the start ofan epidemic to the the average moment when thenumber of infecteds reaches its peak. We see thatby varying return rate we can obtain ten-fold increase in the peak time in the bidirectional model ascompared to the reaction-diffusion model, which ofcourse do not depend on return travel rate and only
on the total flux. Elsewhere [6] we showed analytically that attenuation of the bidirectional epidemic
on a lattice as compared to reaction-diffusion model
is a generic feature of a bidirectional model.

To assess the mutual impact of major travel parameters, i.e. forward and backward (return) travel
rates as well as total flux on the dynamics of bidirectional SIR epidemics we calculated the attack
ratio for various travel parameter values in a lattice of homogeneous locations. The results are presented in Fig. 3. One observes that the global invasion threshold in terms of the total flux rate ω at
low values of travel rates ω + , ω $ still exists in thebidirectional system. This confirms again the similarity of both reaction-diffusion and bidirectionalframework at low travel rates, what we showedelsewhere. However for increasing total flux (going away from the beginning of coordinates), we
observe that for small value of return rates there isa global outbreak, but for increasing return rate wearrive in the region of no global outbreak, even forthe same value of a total flux rate ω. This effectcould not be observed in the reaction-diffusion system, which is fully determined by a total flux, and isspecific for the bidirectional model. Except upper
left region of no epidemic outbreak one can also observe an another smaller outbreak-free region in the
low right corner. This region corresponds to highvalues of the forward travel rates and is unrealistic, because then individuals would spent most of
the time on distant location compromising the notion of a home location. However the effect is very
similar to the case of high return rates, because infected individuals spent so little time at home thatthey could not infect significant number of people
there.

4

Conclusions

Summarizing, we have investigated a bidirectional
epidemiological model, explicitly incorporating thehighly regular movement patterns of human. The
model reflect the tendency of humans to travel
among a few most preferred locations bidirectionally. We systematically compared bidirectionalmodel to the standard, also explicitly incorporating travel behavior of the host, reaction-diffusion
epidemic model on regular topology and complex
networks. We showed that as compared to an
equivalent reaction-diffusion system, bidirectional
travel with the same total fluxes between locations,leads to significant attenuation of epidemic spread.
The global invasion threshold in terms of total flux
4

Book of abstracts for NetMob 201047

References

Attack ratio, log ρ

−1

10

0

[1] Donald G McNeil Jr. Predicting the Flu withthe aid of Washington (Well, George). The
New York Times, May 4th:1, 2009.

−0.5

−2

10

−1

−3

10

−1.5
−4

−

ω /N

10

−2

−5

10

[2] Duygu Balcan, Hao Hu, Bruno Goncalves,
Paolo Bajardi, Chiara Poletto, Jose Ramasco,
Daniela Paolotti, Nicola Perra, Michele Tizzoni, Wouter Broeck, Vittoria Colizza, andAlessandro Vespignani. Seasonal transmission potential and activity peaks of the new
influenza A(H1N1): a Monte Carlo likelihood analysis based on human mobility. BMC
Medicine, 7(1):45, 2009.

−2.5
−3

−6

10

−3.5

−7

10

−4
−8

10

−4.5

−9

10

−8

10

−6

10

−4

ω+/N

10

−2

−5

10

Fig. 3: Attack ratio % in dependence on forward
travel rate ω + and backward (return) travel
rate ω $ for a bidirectional SIR epidemic ina homogeneous one-dimensional lattice oflocations. Black lines corresponds to constant values of the logarithm of the total flux
rate ω. Dark red regions corresponds to an
infection outbreak, dark blue — to the absence of epidemic. Infection rates α = 1,
recovery rate β = 0.1. Lattice consists of
100 nodes with 1000 individuals each. Results were averaged over 50 stochastic realisations.

[3] D Brockmann, L Hufnagel, and T Geisel. The
scaling laws of human travel. Nature (London), 439:462, 2006.
[4] Marta C González, César A Hidalgo, andAlbert-László Barabási. Understanding individual human mobility patterns. Nature (London), 453:779, 2008.
[5] Chaoming Song, Zehui Qu, Nicholas Blumm,
and Albert-László Barabási. Limits of predictability in human mobility.
Science,
327:1018, 2010.
[6] V V Belik, T Geisel, and D Brockmann. The
impact of human mobility on spatial disease
dynamics. In Proceedings of 2009 International Conference on Computational Scienceand Engineering, volume 4, pages 932–935.
IEEE Computer Society, 2009.

between locations known in the reaction-diffusion
framework (SIR epidemic) still exists in bidirectional model at low travel rates. This indicates theequivalence of reaction-diffusion and bidirectional
approaches in this regime. However bidirectional
epidemiological model exhibits a new global invasion thresholds in terms of return travel rates. Evenin the regime of global outbreak in terms of thetotal flux of individuals, high enough return rates
would lead to the extinction of epidemic. In thelight of new findings we convinced that bidirectional model provides a framework for incorporation of the abundance of data on human mobility
available today into comprehensive computational
epidemiological models.

[7] R M Anderson and R M May. Infectious diseases of humans. Oxford university press,
1991.
[8] Lisa Sattenspiel and Klaus Dietz. A structured epidemic model incorporating geographic mobility among regions. Mathematical Biosciences, 128:71, 1995.
[9] Matt J. Keeling and Pejman Rohani. Estimating spatial coupling in epidemiological systems: a mechanistic approach. Ecology Letters, 5:20–29, 2005.
5

Book of abstracts for NetMob 201048

[10] R Albert and A L Barabási. Statistical mechanics of complex networks. Reviews ofModern Physics, 74:47, 2002.
[11] Michele Catanzaro, Marián Boguñá, and Romualdo Pastor-Satorras. Generation of uncorrelated random scale-free networks. Phys.
Rev. E, 71(2):027103, Feb 2005.
[12] G K Zipf. The P1 P2/D Hypothesis: On theIntercity Movement of Persons. American Sociological Review, 11:677, 1946.
[13] Vittoria Colizza and Alessandro Vespignani.
Invasion threshold in heterogeneous metapopulation networks. Phys. Rev. Lett., 99:148701,
2007.

6

Book of abstracts for NetMob 201049

A Tale of Two Cities
Sibren Isaacman⋄ , Richard Becker† , Ramón Cáceres† ,Stephen Kobourov⋆ , James Rowland† , Alexander Varshavsky†⋄

Dept. of Electrical Engineering, Princeton University, Princeton, NJ, USA†
AT&T Labs – Research, Florham Park, NJ, USA⋆
Dept. of Computer Science, University of Arizona, Tucson, AZ, USA⋄†

isaacman@princeton.edu{rab,ramon,jrr,varshavsky}@research.att.com⋆

kobourov@cs.arizona.edu

ious observations about these daily ranges in the two
populations of interest.
Our results show significant differences in mobility
patterns between Angelenos and New Yorkers, and bringout unexpected aspects of human behavior. Our main
observations are as follows:
Fridays are Weekend Days: When considering
daily ranges, Fridays are more similar to Saturdays andSundays and therefore we treat them as weekend days.
Weekends are Varied: Although more daily range
maxima occur on weekends, this does not necessarily
correlate to greater distances traveled on weekends. Our
results show that weekends tend to be more variable
than weekdays. Some people travel less on weekends
and some travel more, when compared to their typical
weekday behavior.
Angelenos Commute Farther: There is a nontrivial differences between the weekday travel patternsof Angelenos and New Yorkers. Specifically, the median
for weekday daily range in LA is 34% larger than in NY,
whereas the 25th percentile weekday LA ranges are 53%
larger.
This trend of Angelenos traveling farther than New
Yorkers continues when examining maximum daily ranges.
Our results show that people living in the LA area travel
about 20% farther than those from the NY area, regardless of the percentile considered.
Commuting Estimates: The median daily rangeof people in the greater NY and LA regions are 3.8 and
5.0 miles, respectively. Moreover, as shown in Figure 1,
cell phone users in downtown LA have median daily
ranges that are nearly double those of their Manhattan
counterparts.
Interestingly, even though the data released by the
US Census Bureau [6] indicates that people in NY havethe longest commutes in the nation by time, our datasuggests that people in NY have significantly shorter
commutes than people in LA by distance. If not nec-

Characterizing human mobility patterns is critical toa deeper understanding of the effects of human movement. For example, the impact of human travel on
the environment cannot be understood without such acharacterization. Similarly, understanding and modeling the ways in which disease spreads hinges on a clear
picture of the ways that humans themselves spread [2].
Other examples abound in fields like urban planning,where knowing how people come and go can help determine where to deploy infrastructure [1].
Human mobility researchers have traditionally reliedon surveys and observations of relatively small numbers of people to get a glimpse into the way that humans move about, for instance by studying airline flightpaths [4]. These methods often result in small sample
sizes and may introduce inaccuracies due to intentionalor unintentional behaviors on the part of those being
observed. However, with the advent of cellular wirelesscommunication, ubiquitous networks are now in placethat must know the location of the millions of active cell
phones in their coverage areas in order to provide thephones with voice and data services. Given the almost
constant physical proximity of cell phones to their owners, location data from these networks has the potential
to revolutionize the study of human mobility.
In this work, we explore the use of location information from a cellular network to characterize humanmobility in two major cities in the United States: Los
Angeles (LA) and New York (NY). More specifically, we
analyze anonymous records of approximate cell phone
locations at discrete times when the phones are in active use. Our data set spans two months of activity for
hundreds of thousands of phones, yielding hundreds ofmillions of location events. We then compile aggregate
statistics of how far humans travel daily. We introduce
the concept of a daily range, that is, the maximal distance that a phone, and by assumption its owner, hasbeen seen to travel in one day. Finally, we make var1

Book of abstracts for NetMob 201050

1. REFERENCES

essarily contradictory, our data indicates that commuting is done differently in NY and LA. It is possible thatgenerally slower forms of transportation, such as public transport or walking, are responsible for the longcommute times reported in NY.
City of Neighborhoods: We found that variations
in mobility are striking even between subareas of thesame city. Within LA, variations span from 1.3x (at themedian) to 3x (at the 98th percentile). The differences
within LA itself are thus equal to, or perhaps even a bit
greater than, differences between LA and NY.
Differences within NY are even greater — variations
span from 1.8x (at the 75th percentile) to 4.2x (at the98th percentile). The map overlays in Figure 2 also
show that LA is more self-similar than NY.
Manhattanites Travel Very Far: Examining maximum daily ranges only for residents of the city centersreveals an interesting reversal of the general pattern ofAngelenos traveling farther than New Yorkers. Herethe medians are at 69 and 29 miles for Manhattan anddowntown LA, respectively. For the 75th percentiles thecorresponding numbers are 735 and 129 miles. These
numbers show that when Manhattanites travel far, they
travel very far and farther than Angelenos.
US vs Unnamed European Country: It is possible to compare some of our statistics to those computed
by González et al. for an Unnamed European Country(UEC) [3]. Our maxima show that in the greater LA
area, 50% of people traveled more than 36 miles on
at least one day, and that in the NY area 50% traveled more than 27 miles. This is in sharp contrast to
González et al.’s findings that nearly 50% of all the people in their study remained within a 6-mile range overa 6-month period. The LA maxima are more than 5xlarger than those in UEC and the NY maxima are morethan 4x larger. While it is not surprising that the numbers in the US are larger, as the US is more car-oriented,
the magnitude of the difference is unexpected.
Overall, we conclude that the study of operational
records from cellular networks holds great promise forthe large-scale characterization of human mobility patterns without compromising individual privacy. For
more details on our data set, our analysis methodology,
and our results, we refer the reader to our full paper [5].

[1] The journey to work: Relation between
employment and residence. Technical Report No.
26, American Society of Planning Officials, May
1951.
[2] D. Brockmann, V. David, and A. M. Gallardo.
Human mobility and spatial disease dynamics.
Proc. of the Workshop on Social Computing with
Mobile Phones and Sensors: Modeling, Sensing
and Sharing, Aug. 2009.
[3] M. C. González, C. A. Hidalgo, and A.-L.
Barabási. Understanding individual humanmobility patterns. Nature, 453, June 2008.
[4] R. Guimera and L. Amaral. Modeling theworld-wide airport network. Eur Phys J B, 38, Jan.
2004.
[5] S. Isaacman, R. Becker, R. Cáceres, S. Kobourov,
J. Rowland, and A. Varshavsky. A tale of twocities. Proc. of ACM Workshop on Mobile
Computing Systems and Applications (HotMobile),
Feb. 2010.
[6] US census data. Downloaded fromhttp://www.census.gov.

2
Book of abstracts for NetMob 201051

(a) Manhattan(b) Downtown Los Angeles

Figure 1: Maps giving a visual representation of the median daily ranges of cell phone users in Manhattan anddowntown Los Angeles. The radii of the inner, middle, and outer circles represent the 25th , 50th , and 75th percentiles,
respectively, of these ranges across all users in a city. Ranges for all users in a city are made to originate in a common
point for clarity of display. The two maps are drawn to the same scale.

(a) New York and New Jersey subregions(b) Los Angeles subregions

Figure 2: Maps giving a visual representation of the median daily ranges of cell phone users in subregions of the
LA and NY metropolitan areas. The radii of the inner, dashed, and outer circles represent the 25th , 50th , and 75th
percentiles, respectively, of these ranges across all users in a subregion. Ranges for all users in a subregion are madeto originate in a common point for clarity of display. The two maps have different scales.

3Book of abstracts for NetMob 201052

Workshop on the analysis of mobile phone networks / Tuesday May 11, 2010 (MIT,
Cambridge, MA / USA)
Davy Janssens, Professor at Hasselt University
davy.janssens@uhasselt.be
Sjef Moerdijk, doctorate researcher at Hasselt University
sjef.moerdijk@rws.nl

Title: Predicting travelling activity space based on phoning activity space in social networks
For the last decade, activity-based models have set the standard for modelling travel demand.
The idea behind these models is that travel demand is derived from activities that individuals
and households need or wish to perform. As a result of this, travel in itself is often also
derived in these models by means of simple categories of travel, such as commuting, leisure,or business, as if these activities exist separate and are self-contained.
Only recently, social networks have been added to these traditional classifications, as a new
possible predictor of travel behaviour and movement. Researchers such as Urry and others(see Urry, 2006; Sheller, 2006; Larsen, 2006) ) have argued that flows and meetings of people
produce small worlds which require connections and meeting places; a phenomenon which isalso known as the new mobilities paradigm. The paradigm states that mobility of people inour postmodern era is no longer restricted to ‘corporeal mobility’ in which people (and goods)
have face-to-face contacts. These contacts are extended and complemented with contacts
mediated by interfaces like mobile phone, e-mail, Blackberry, etc. the so called ‘face-tointerface-to-face’ contacts. In trying to understand this completion, one should focus on theinteraction and ‘interconnections’ (Larsen, 2006) between these mobilities. In other words:
travel and social meetings require systems of coordination using virtual and communicative
travel in-between physical travel and meetings. With this understanding of social networks asa facilitator of virtual as well as physical networks and the movements within them, travel
becomes a result of human networking (see for some research on how to model this Dugundji,
2008; Axhausen 2008; Arentze 2008).
ICT developments have enabled communication with distant others without physical copresence, which makes that ‘face-to-face’ meetings are not a prerequisite to build or maintainsocial contacts any more. A large body of literature on the transportation impacts of specific
ICT applications has been produced. Although recent publications from physics seem to provethe contrary, it is widely believed in transportation research that it is crucial to understand thegeography of the social networks to which the travellers belong, if one wants to understandthe destination choices of the travellers. Recently, Mok and Wellman (2007) have contributed
to this line of research. Axhausen has shown for instance how to examine distance decayfunctions and market shares of face-to-face meetings, phone, e-mail and SMS (see Axhausen,
2004, 2007). Axhausen and Frei (2007) have shown geographical size and structure of global
social networks, where Frei and Axhausen have shown distance decay of different new media
that are used in maintaining the social network.

While these papers contribute a lot to the understanding of the spatial distributions ofindividuals, they do not lay emphasis on the relationship between virtual and physical travel

Book of abstracts for NetMob 201053

in social networks on the one hand and the corresponding spatial and temporal distributions
on the other hand.
The main research question that we therefore want to address is whether behaviour in terms ofactivity-space use by social network members can be explained (or predicted) by their usageof new ICT means in general and mobile phone in particular. To the best of our knowledge,
this is the first study that aims to examine the relationship between a travel activity space anda phoning activity space (in short defined here as the square area that a person would have tocover if he wanted to meet distant others all over this area face-to-face, and as a fact now ishaving contact with by mobile phone contact (in other words: ‘virtually meeting’). This theface-to-interface-to-face contact) and the travelling activity space for members that belong to
the same social network (with the ‘ego’ as the central person, surrounded by his ‘alters’). If
such a relationship can be found, phoning activity geographies can be used as an
approximation (or prediction) for travel geographies, leading to more and larger quantities ofdata (and thus potentially lower error-bounds) that can be relied upon for training and testing
the derived activity-spaces in model environments, given the large inflow of spatial-temporal
information which can be extracted from mobile devices. The methodology could contributeto the existing literature and research that has been carried out in the field of individual
accessibility measures, and may finally be used as input for a destination choice component ofactivity-based travel demand models. Apart from the obvious applications in transportation
models, added insight can also lead to a better understanding of the basic laws governing
human mobility. Indeed, as many scientists have pointed out, the goal of social sciences is not
simply to understand how people behave in large groups (as it was studied in Gonzalez et al.
2008), but to understand what motivates individuals to behave the way they do (Editorial
Nature, 2008).
The main research goal that has been outlined above (degree of possible prediction of
travelling activity spaces based on phoning activity spaces by social networks members),
needs to be further specified in two additional specific research questions.
First of all, one obviously needs to know how the geographies of mobile phone usages by
travellers that maintain social networks look like.
Secondly, one is obviously also interested in what kind of usages of mobile phone during
travelling show maintenance of social networks and what usages don't show maintenance.
In the workshop we want to focus on the construction of social network and phoning
geographies, relying upon existing measures of spatial distributions that are based on daily
activity spaces. We want to higlight some (im)possibilities in this context. The results of afirst analysis are focused on the relations between mobile phone usage and travelling. For
instance how much distance respondents travel compared to their phoning distances.
We found that the following points need to be addressed further:- The new mobilities paradigm is about corporeal, digital, virtual and even mental
mobilities. All these mobilities show coordination patterns, interactions, etc. So far,researchers and scholars have focussed on corporeal travel and mobile phoneinteractions, partly because the data availability, partly also because of the fact that
corporeal travel and mobile phone are both mobile. These spatial and temporalinteractions are self-evident. But e-mail use has become mobile as well (for instanceBlackberry, mobile internet via mobile phone, etc.), so the spatial and temporalinteraction of corporeal travel, mobile phoning and e-mailing looks very interesting.

Book of abstracts for NetMob 2010

54

-

-

So we are looking forfeasible data sources to use for constructing the spatial andtemporal interactions.
Social networks are maintained by human interactions. For instance by phoning or
e-mailing each other (and consequently after a while meeting each other face-to-face).
We still need to find out how to present such multi-interaction manifestations, what is
a useful way to present social networks and ‘their’ multi-level (or: corporeal anddigital and virtual and even in a conceptual way mental!) mobilities?
One of the main methodological issues in these humanistic studies concerns thedifference between stated preferences (‘I’m use my phone five times a day’ etc.) andrevealed facts (an individual using his phone six times a day). In a more general way
we still need to discuss which survey methods can be validated with these revealed facts(which don’t) and how these validation should be developed.

References
Larsen, J., J. Urry, & K.W. Axhausen (2006), Mobilities, networks, geographies. Ashgate,
Aldershot.
Urry, J. (2006), Sociology beyond societies: mobilities for the 21st century. London,
Routledge.
Sheller, M. & J. Urry (2006), The new mobilities paradigm. Environment and Planning A 38(2), pp. 207-226.
Frei, A. & K.W. Axhausen (2007), Size and structure of social network geographies.
Arbeitsbericht Verkehrs- und Raumplanung, 439, IVT , ETH Zürich, Zürich.
Axhausen, K.W. (2004), Social networks and travel: some hypotheses . CD-ROM of theconference on progress in activity-based analysis, Maastricht.
Axhausen, K.W. & A. Frei (2007), Contacts in a shrunken world. Arbeitsbericht Verkehrsund Raumplanung, 440, IVT , ETH Zürich, Zürich.
Mok, D. , Wellman, B. and Carrasco, J. , 2008-07-31 "Does Distance Matter in the Age of theInternet: Are Cities Losing Their Comparative Advantage?
González, M.C., Hidalgo, C.A. and Barabási, A.L. , Understanding individual human mobility
patterns (2008), Center for Complex Network Research and Department of Physics andComputer Science.

Book of abstracts for NetMob 201055

Workshop on the Analysis of Mobile Phone Networks
Tuesday, May 11, 2010, MIT (Cambridge, MA)

Preliminary findings on application of mobile phone data analysis to urban studies
Fabio Manfredini*, Paola Pucci, Paolo Tagliolato, Paolo Dilda
Dipartimento di Architettura e Pianificazione (DiAP)
Politecnico di Milano* corresponding author: fabio.manfredini@polimi.it

In recent years, a new approach for estimating people's movement in cities through mobile
phone traffic analysis has been developed. Compared to the traditional methods of urban
surveys, the use of aggregated and anonymous cellular network log files appears to be a
promising tool for large-scale studies with notably smaller efforts and costs.
In particular, the use of mobile traffic phone data shows many advantages, for example:-

large data samples, proportional to the pervasiveness of mobile phone use;monitoring of any area, given the extent of mobile phone network coverage;
generation of data almost in real time;high spatial and temporal resolution, compared to traditional and institutional data
sources.

However, despite the positivist approach to the new methodology, additional evidence isneeded to show how cellular network signals correlate with the actual presence of people inthe city, how this source of information can be used to characterize and to map different urban
situations and their occupants and how this tool could support urban planning and urban
policies.
The presentation will deal with this topic by showing the results of a research carried out by a
Department of Architecture and Planning of the Politecnico di Milano research team, during
the 2009, for Telecom Italia, the main Italian mobile phone operator.
Purpose of this paper is to address this shortcoming by presenting the results of a survey
effectuated with Telecom's cell-phone-network data in Lombardia Region (Italy) during theyear 2009, as a promising approach for characterizing and mapping urban domains and theiroccupants, assisting traditional databases and analyses of urban dynamics.
The aim was to assess the contribution of cellular phone traffic data for understanding andanalyzing urban dynamics and to propose possible uses of this kind of information in urban
planning.
In order to analyze the complex temporal and spatial patterns of mobile phone activity, wewere given access to data covering the whole Lombardia Region (Northern Italy), provided by
Telecom in form of Erlang, a measure which describes the mobile phone activity as a functionof position and time, recorded at a spatial resolution of about 250 meters, every 15 minutes in
the period January -October 2009.
The first step of our research was the analysis of mobile phone activity trends for somealready known urban sectors, subjects of previous research, selected on the basis of present
land-use patterns of population and activities, densities and socio-economical profiles. For
each of these urban situations we studied the Erlang trends during a typical week, to verify
temporal and spatial patterns of cellular phone usage for similar urban sectors in terms of
population and activities characteristics.

Book of abstracts for NetMob 2010

56

The results show that mobile phone activity patterns can provide useful information forinterpreting the specific dynamics of different urban situations such as monofunctional
residential zones, railway stations, urban sprawl areas, factories.
In the second step of the research, we focused on the reliability of Erlang data with respect totraditional data sources.
We therefore compared mobile phone data of the main cities of Lombardia Region and their
population dynamics1 during a typical weekday and we found a strong correlation between
these variables proving the potentialities of Erlang data for describing the variability of dailychanges of urban population at the municipality scale.
We also worked on mobile phone traffic data at the Milano urban region scale2, during the2009 International Design Week, a leading event which concentrates its activities in the Fair
area and in hundreds of places within and outside the city.
We therefore performed several analysis to evaluate the potential contribution of Erlang data
to describe, to represent and to manage an event, from the beginning until its conclusion. We
mapped and interpreted the spatial configuration of mobile phone activity in order to highlightwhich parts of the city showed a significant concentration of traffic comparing the days whenthe event occurred with other days without events.
We defined a set of significant spatial operations between Erlang matrixes aimed at underline
the territorial effects at a wider scale and at different temporal patterns of the event such as,
for example, ratio between nighttime and daytime mobile phone activity, ratio between
weekdays and holidays.
This type of information, if suitably interpreted, may be useful to assess the consequences of a
specific event on the entire urban system in its spatial and temporal patterns and to evaluate
its impacts on the whole urban system (mobility, congestion, tourism).
Urban planning traditional data sources are mainly based on static statistical surveys and are
not able to catch the variability in the intensity of urban space’s use by present population.
Further analysis focused on the correlation between the intensity of telephone calls at certain
times of the day with the spatial configuration of residents and workers in the Milan area.
Preliminary results showed that telephone traffic data can effectively help to represent and todescribe, dynamically over time, the intensity of activities and of presences at the urban scale.
Because of its spatial and temporal resolution, mobile phone data constitute an interesting andunique source of information on urban uses. Indeed, if we consider the observed andaggregated telephone traffic as the result of individual behaviors and habits, we conclude thatmobile phone data can provide information, which changes over times, on urban contexts, andcan bring to new interpretation of urban dynamics.
This study therefore suggests that cell-phone-network data has the potential to drasticallychange the way we view and understand the urban environment.

1

The latter was obtained from a traditional mobility data-base, the 2002 Lombardia Region OriginDestination survey, which is widely used in urban and traffic studies.
2

The Milano Urban Region is defined as an extended region that go far beyond the traditional
administrative structure. Milan is the main center of the urban region which is characterized by astratum of dense urbanization stretched over the ancient framework while the bordering provinces
have been incorporated in the strongly urbanized and enlarged urban region.

Book of abstracts for NetMob 201057

Secondly, it explores whether mobile network data can reveal the significant time-dependent
variation which is missing from traditional analysis and can thus describe cities dynamicallyover time.
Another conclusion is that urban planning competences, together with specific knowledge on
urban systems and on the distribution of activities and population within the territory areneeded to correctly interpret mobile phone data and to characterize and to map urban contexts
and their occupants.
In the final phase of the research activity, we presented our work to different stakeholders,belonging to private and public sectors in order to collect ideas and proposals on possible
applications of this approach to different topics such as event management, civil protection,
mobility monitoring, urban rhythms analysis and mapping; we have seen a great interest frommost of them in terms of the potential contribution of this data to provide new decision tools
for the development of action and policies in different sectors.
Main references
Ahas, R., & Mark, U. (2005). Location based services - new challanges for planning andpublic administration? Futures , 37, 547-561.
Caceres, N. Wideberg, J. P. Benitez, F. G. (2007). Deriving origin-destination data from a
mobile phone network. Iet Intelligent Transport Systems, 1 (1), 15-26
Gonzalez, M. C., Hidalgo, C. A. & Barabasi, A-L (2008). Understanding individual humanmobility patterns. Nature, 453, 779-782.
Reades, J., Calabrese, F., Sevtsuk, A., & Ratti, C. (2007). Cellular Census: Explorations in
Urban Data Collection. IEEE Pervasive Computing , 6 (3), 30-38

Book of abstracts for NetMob 201058

Analyzing cell-phone mobility and social events
Francesco Calabrese∗, Giusy Di Lorenzo∗ , Francisco Pereira∗ , Liang Liu∗ , Carlo Ratti∗
2 Extracting Preferences for Social Events
Location-based services and traffic planning may benefit To determine the social events people living in certainfrom predicting leisure preferences for people living in a areas go to, we use two datasets:
Abstract

particular location. To make such predictions, surveys areoften administered, but surveys are notoriously expensive
and easily become out-of-date. Recently, researchers haveproposed to automate the process of extracting preferencesby analyzing user-generated content. Here we propose to
analyze digital information that is implicitly generated byusers while they carry their mobile phones. We show that, by
analyzing mobility traces we are able to associate locations
with travel demands for different types of social events.

• Location of Mobile Phones. We process 130 millions
of anonymous location estimations - latitude andlongitude - from roughly 1 million mobile phones
in greater Boston (an area of 15km2 ). The dataset
consists of anonymous cellular phone signaling datacollected by AirSage [4]. The finest-grained estimation of location we are able to achieve is represented
by a cell of 500 x 500m2 .

• Boston Globe website. We crawl the “Boston Globe
Introduction
Calendar” website to extract social events. This
According to the US Federal HighwayAdministration
website is a reputable and comprehensive list of soa “special event” is an occurrence that “abnormally incial events in Greater Boston (more than 500 daily).
creases tra!c demand,” unlike an accident, or construcThe events are organized in 14 categories: Arts &tion and maintenance activities, which typically restrict
Crafts, Business & Tech, Community, Dance, Eduthe roadway capacity. Planned Special Events (PSEs)
cation/Campus, Fairs & Festivals, Food & Dining,
include sporting events, concerts, festivals, and convenMusic, Other, Performing Arts, Shopping, Sports
tions at permanent multi-use venues. They also include& Outdoors, Visual Arts, and Cinema.
less frequent public events, such as parades, fireworks
By using those two datasets, we generate pairs ofdisplays,bicycle races,seasonal festivals,etc.
The often mentioned outburst of mobile phones the type:
during late 20th century accompanied by the more
• home|destination - For each user, we determine
recent trend of sensors and advanced communication
her home location and her set of destinations, i.e.,systems (e.g. GPS, digital cameras, Bluetooth, WiFi)
we extract trajectories and generate tuples of theallow for unforeseen amounts of data from urban areas
form home|destination. Our dataset contains
through which to study both groups [1], individuals
location estimations for mobile phones. To extract[2] or both [3]. On the other side, the emergencemobility traces from location estimations, for eachof web 2.0 techniques, especially geospatial enableduser, we infer her stops (places where the user has
web services, such as upcoming.org, etc, enables the
stopped for more than an hour), and we then collectcitizens organize and inform the audience in a real time
the trajectories that originate from those stops. A
way. The convergence of these two trends in ubiquitous
trajectory is set of subsequent physical locations
computing open a new opportunity and challenge tovisited by the user such that the time interval
understand the travel demand triggered by PSE.
between two subsequent points is less than twelve
In our work, we analyse fine grain anonymized indihours. We pick the user’s home location to be thevidual mobility information for travel demand forecastmost frequent stop at night (i.e., between 10pm anding in the context of PSE [5]. Both the process followed
7am).
and the data precision are thus far novel and unique to• destination|event – We associate destinations
our knowledge.
with types of social events by crawling the event
section of the “Boston Globe” website. We selectthe destinations (other than home locations) at∗ MIT Senseable City Lab, fcalabre@mit.edu
which users stay while big social events are taking
1Book of abstracts for NetMob 201059

(a) Boston Red Sox vs. Bal- (b) Shakespeare on thetimore Orioles at Fenway Boston Common, 2009-8-13
Park, 2009-9-9

Figure 1: Examples of events in Boston. Figures show
the locations of the events (diamond) and estimatedorigins distribution of people attending the events:
shade from light (low) to dark (high).

attending to one type of event are most probably notattending the other type of events, showing a complementary role of sports and arts events in attracting different categories of people.
Since the origins of people attending an event arestrictly related to the location and type of events, we argue that by using just this information we would be able
to predict the type of event. If a relationship between
origin of people and type of event is found, it would bepossible to determine the abnormal and additive travel
demand due to a planned event by just considering thetype of that event. It would then be possible to provide a city with critical information on which to takedecisions about changes in the transportation management, e.g. increasing the number of bus lines connecting
certain areas of the city to the venue of the event.
In the next section we will show 8 different models
that we have developed to perform the prediction of thetype of event starting from the mobility data associatedwith it.

place. We consider only users who stay for at least
70% of an event duration, and only events that are“unique” - no other big event is taking place within
the radius of 1 km at the same time. In so doing, weare able to create tuples that associate destinations 3.1 Prediction The task at hand is to understandwith social events. This results in 58 types of social the relationships between events and origins of people. Particularly, we seek for the predictive potential
events across 7 locations [5].
of events in respect to mobility phenomena. This can• home|event - We combine pairs in the previ- be seen from two perspectives: a classification task inwhich we want to understand how a vector of features
ous two points (home|destination pairs anddestination − event pairs) to obtain, for each (e.g., attendees origin distribution) predicts a classificahome location, the list of types of social events its tion (e.g., an event name or type); a clustering task, inwhich the feature vectors are distributed according toresidents go to.
similarity among themselves.
We used the Weka open source platform [6], which
3 Methodology
contains a wide range of choices for data analysis. For
Our methodology for describing events through mobility
classification, we use a Multilayer Perceptron, with one
choices is based on the use of the estimated origins ofhidden layer and the typical heuristic of (classes +people attending to the events. Figure 1 shows some
attributes)/2 for the number of nodes. For clustering,
examples of spatial variation of the estimated origins of
we apply the K-Means algorithm (with K = # event
people attending different events.
types or K = # event places). In each experiment,
Sport events such as baseball games attract about
we used 10-fold cross-validation, in which a tenth of the
double the number of people which normally live indataset is left aside for testing the algorithm while using
the Fenway Park area. Moreover, those people seemthe remaining for training. This train-test process is ran
to be predominantly attended by people living in the
10 times (one for each tenth of the dataset).
surrounding of the baseball stadium, as well as the south
Boston area (Figure 1(a)).
4 Experiments
Performing arts events such as the “Shakespeareon the Boston Common” (Figure 1(b)) which his held We aggregated attendees in terms of zipcode area andyearly, attract people from the whole Boston metropoli- distance to event, discretized in 2000 bins. We did sotan area, and very strongly people which live in the im- because if we were to use a geographic coordinate of
mediate surroundings of the Boston Common (average individuals, the resulting data would be sparse. Instead,distance lower than 500 meters). The number of people by aggregating data geographically, we could find usefulattending the event is instead about 1.5 times greaten patterns. To avoid the strong bias towards attendees in
the neighborhood of the event, we also remove thosethan what it is usually found in the Boston Common.
By comparing the two images in Figures 1(a) and that live in the same area of the event (their home1(b) it is easy to understand that most of the people location falls in the same 500m x 500m cell of the event)Book of abstracts for NetMob 201060

because we would not be able to distinguish between
event and home.
For each event, we created an instance that contains
the corresponding attendee origin pattern distribution,
evaluated at the level of the zipcode area (with average
size of 4.5km2 ). For example, for one showing of
the Shakespeare’s “Comedy of Errors” at the Boston
Common, we have 96 attendees (users monitored by thesystem, with a share of about 20% of the population)and then count the total number of people coming fromeach zipcode. Our goal is to test whether similar eventsshow similar geographical patterns. More specifically,
given origin pattern distribution, the goal is to predict
the type of event.
We met this goal by testing 3 prediction models,
and we measure their accuracy in terms of fraction ofcorrectly identified event types.
Before training our algorithms, we analyzed theoverall distribution of events to get the classifier baselines. The principle is to know the accuracy of a classifier that simply selects randomly any of the 5 event
types or that always chooses the same event type, anduse them as a baseline to compare for the improvementof the quality. The average value of this baseline is23.34% (standard deviation of 4.03) for random classification. Differently, if the classifier chooses the eventwith highest probability (performing arts), the accuracy
will be 35%. The first experiment was to use all vectors
as just described, applied to a Multilayer Perceptron.
The result is a surprising 89.36% of correctly classified
events in the test set. From the clustering analysis, we
see that mostly attendees come from the event’s zipcodearea, suggesting that people who live close to an eventare preferentially attracted by it. To focus on effects
other than close proximity, we created a new prediction
model considering only people coming from zipcode different from the event’s.
The result is 59.57%, which still indicates therecurrence of origin patterns for events of the same type.
A clustering analysis brings the distributions that we
can see in Figure 2.
5

Conclusions

Based on our analysis of nearly 1 million cell-phone
traces we correlated social events people go to with theirhome locations. Our results show that there is a strong
correlation in that: people who live close to an eventare preferentially attracted by it; events of the same
type show similar spatial distribution of origins. As aconsequence, we could partly predict where people will
come from for future events.

(a) Cinema(b) Family(c) Music(d) Performing arts(e) Sports

Figure 2: Spatial visualization of clusters centroids.
The circles correspond to the zipcode areas with value
greater than zero. The shade from light (low) to dark(high) is proportional to the value.
[1] J. Reades, F. Calabrese, A. Sevtsuk, and C. Ratti,“Cellular census: Explorations in urban data collection,” IEEE Pervasive Computing, vol. 6, no. 3, pp.
30–38, July-September 2007.
[2] M. C. Gonzalez, C. A. Hidalgo, and A.-L. Barabasi,“Understanding individual human mobility patterns,”
Nature, vol. 453, 2008.
[3] N. Eagle and A. Pentland, “Reality mining: sensing
complex social systems,” Personal Ubiquitous Computing, vol. 10, no. 4, pp. 255–268, 2006.
[4] Airsage,“Airsagewise
technology,”
http://www.airsage.com/.
[5] F. Calabrese, F. Pereira, G. DiLorenzo, L. Liu, andC. Ratti, “The geography of taste: analyzing cellphone mobiloty and social events,” in International
Conference on Pervasive Computing, 2010.
[6] I. H. Witten and E. Frank, Data Mining: Practicalmachine learning tools and techniques, 2nd Edition.
Morgan Kaufmann, 2005.

References

Book of abstracts for NetMob 2010

61

MobNet 2010 Proposal: PARIS BY NIGHT

Paris by Night
Weekends urban activity via mobile phone data
Christophe Carioua, Cezary Ziemlickib & Zbigniew Smoredaba.

b.

EVERYDATALAB, Rennes, France (christophe.cariou@everydatalab.com)
SENSe/Orange Labs, Paris, France (cezary.ziemlicki, zbigniew.smoreda@orange-ftgroup.com)

Abstract - We use mobile phone data to study the impactof two weekend festivals – Fête de la Musique and Nuit
Blanche – on the city of Paris compared with a standard
weekend. Using the mobile data we can study collective
dynamics in the city and separate normal fluctuations fromanomalous fluctuations, i.e. spatio-temporal changes causedby the two events. We also detect cultural scenes, allowing
us to more precisely identify urban usages and the relative
audiences for the different events in each festival.
Keywords - Mobile phone data, complex networks, urban
dynamics.

incoming and outgoing calls, the handovers (cell changes)
during a call and the incoming and outgoing text messages.
Finally, the data are collected by antennas in real time.
The data can be considered to be representative of thecommunication activity of Ile-de-France residents. Orange
has a market share of around 40% and mobile penetration inIle-de-France is around 120%. We therefore have access tothe communications made entirely or partially within the cityof Paris by, respectively, 1,148,552, 1,143,687 and 1,163,273
anonymous individuals during Fête de la Musique, Nuit
Blanche and the standard weekend.
The mobile phone network

Introduction
The Economist recently devoted an issue to «The Data
Deluge», the vast potential of the exponential availability ofmassive volumes of digital data [1]. These data are
increasingly used to reveal urban dynamics in ever morerefined spatial and temporal terms [2]. In recent years, works
were developed to reveal the pulse of the city - Milan [3],Graz [4], Rome [5], New-York [6] - and to understand
individual and collective movements [7-9]. The mobile
phone data were also mixed with transport data [5], businessdata [10], photo activity [11]... The introduction is detailed
in the paper but outlined in this abstract. In particular, we
present the sociological characteristics - differences,similarities and regularities - of the two events for Paris,
explaining the choice of methods deployed in the paper.

All the measurements were collected by Parisianantennas. The Paris mobile network is made up of 3,692
antennas on 1,365 cell sites; we only have these cell sites'
geolocation. We take each cell site to cover a Voronoi region:
every point in the diagram is at an equivalent distance fromthe cell sites [12]. The area of the city is 105km2, while thearea covered by the network is a little larger – 127km2 –because of boundary effects. This technique breaks the city
down into small areas equivalent to 300m x 300m squares.

From communications to paths
The mobile phone data
We have access to data provided by the Orange
operator for the weekends of Fête de la Musique, an annual
national music festival (June 21-22 2008) and Nuit Blanche,
an art festival (October 04-05 2008), and a weekend when
there was no event liable to have a major impact on the city
(October 18-19 2008). For each weekend the data areanonymous and include the start and end time of the

Figure 1. The mobile phone network - nodes (yellow) and edges (blue).

1

Book of abstracts for NetMob 2010

62

MobNet 2010 Proposal: PARIS BY NIGHT

We constructed the Paris mobile network in thefollowing way. We see the cell sites as nodes in the mobile
network; it is important to remember that each site is madeup of several antennas. The edges in the network are thus all
the existing connections between the adjacent sites. The
length of each edge is measured very simply by thegeographic distance between the furthest sites. This gives us
a spatial network of 1,365 nodes and 3,979 edges. [Figure 1]
In conclusion, we studied the city of Paris purely in theform of its mobile network.

difference between Fête de la Musique and the standard
weekend is substantially greater: the extra activity during theSaturday morning continues during the afternoon; there is afurther peak between 9 and 11pm. The apparently greatest
impact of Fête de la Musique is observed on Sunday; Paris’collective hangover is a repercussion of this. Thisconsiderable difference on Sunday thus explains the lower
number of trajectories for Fête de la Musique. Finally, it isworth noting that the city does not switch off during thenight from Saturday into Sunday, unlike the previous night.

Individual dynamics

255 000

We consider all the measurements collected to be thelocations of an anonymous individual at a given moment oftime, whatever the communication type. We focus onperiods of fifteen minutes rather than on real time. As aconsequence, we duplicate the communications which are
spread over several quarter-hour periods. We then transformthe communications into individual trajectories: each end ofa call and start of the next call thus become an individual’s
trajectory, giving us a set of trajectories performed byindividuals geo-located by the antenna they are using.
As we do not have the geographic location of theantenna, we make the following adjustment. The variable
Piik(T) measures: on the one hand, the static presence of anindividual using an antenna located on a cell site i, and on
the other hand, the path made by an individual between
antennas in a single cell site i. The variable Piik(T) thus
measures the path made by an individual k between two
antennas located in two different cell sites i and j. These twodifferent cell sites must be adjacent. When this is not thecase, we use the A* algorithm to predict trajectories [13]: theshortest path between an initial node and a final node(adjacent cell sites), taking into account the geographic
distance between the two nodes. Another predictive
algorithm could have been used; we chose this one forreasons of simplicity. Finally, we eliminated all the
duplications of one individual during a fifteen-minute period.
In conclusion, we have, respectively, 19,355,414,
20,671,622 and 20,944,771individual trajectories for Fête dela Musique, Nuit Blanche and the standard weekend.
Collective dynamics
In this paper, we are not interested in individual
dynamics but rather in collective dynamics within the city ofParis. We aggregate these trajectories in terms of nodes andedges in the mobile network:

Figure 2 shows the temporal dynamic of these
trajectories for the three weekends. If the three weekends do
not really differ in terms of the total number of traces, then
the temporal profiles will give us relatively little
information. The profiles are similar: the difference between
Nuit Blanche and the standard weekend is slight, and there isnothing to suggest that it is caused by the event itself. The

205 000
155 000
105 000
55 0005 000
00:00 04:45 09:30 14:15 19:00 23:45 04:30 09:15 14:00 18:45 23:30
Figure 2. The total number of paths : Fête de la Musique (blue), Nuit
Blanche (green) and Standard Week-End (red).

From routines to events
The impact of the two events on the city compared witha standard weekend cannot be analysed using the previous
approach. We therefore think it is worthwhile to extend theanalysis by distinguishing normal fluctuations fromanomalous fluctuations.
Normal versus anomalous fluctuations
Mobile data have already been used to draw adistinction between fluctuations at city level [14]; we
adapted it to our particular context. Indeed, we have just one
standard weekend as a reference. The number of anomalous
paths AP measures the discrepancy between urban behaviour
during the events EP and during the course of the standard
weekend NP:
Anomalous behaviour will thus be defined bycomparison with the standard deviation:

σ (T ) =1.∑ ij Aij (T )2N

We take into consideration the fact that we only have
one standard weekend as a reference: the error is thus 25%.
Anomalous fluctuations are defined as follows:

APij (T ) ≥ 0.25.σ (T )We also take into account the fact that the measurement
taken at a cell site is much higher than between sites; we2Book of abstracts for NetMob 2010

63

MobNet 2010 Proposal: PARIS BY NIGHT

therefore perform the previous calculation separately for thetwo situations and then reaggregate them.

Figure 3. Standard Week-End: the normal fluctuations.
Saturday, 10:45pm.

Musical and artistic dynamics
Figure 2 (red curve) and Figure 3 show the normal
fluctuations seen for the city of Paris, in other words during
the standard weekend. The urban dynamic is fairly
conventional for a weekend: at night the city never switches
off, unlike on weekdays; Sunday differs greatly from theother days of the week, particularly in the afternoon. Figure
4 shows the anomalous fluctuations caused by the two eventsin the city of Paris.

later, between 11.15 and 11.29pm: there are thus as many
anomalous fluctuations as normal fluctuations. During thisperiod, Fête de la Musique doubles the number of completed
trajectories. In this way the highly popular event extends theParisian evening. This later-than-normal time marks the endof part of Fête de la Musique: the very large mass concerts
for young people and families in particular.
Then, during the night and until the following morning,anomalous fluctuations still account for half of normal
fluctuations. The impact is therefore still very great. It is lessthan previously noted, because of a high number of people
leaving and a lower population density at the different
venues as the night progresses. The after-effect of this event
is seen on Sunday, with very strongly negative abnormal
fluctuations. The city of Paris never really reawakens during
Sunday, an upheaval which extends until Sunday evening.
Nuit Blanche also has a major impact on the city, but toa lesser degree: it never reaches the same magnitude as Fêtede la Musique. The impact of the latter is much greater thanthat of the former. Figure 5 shows the correlation between
the fluctuations during the two events in fifteen-minuteperiods. There is a very good quality purely linear
relationship, with an R2 of 0.83. It is also high: the impact ofFête de la Musique is on average 6.3 times greater than thatof Nuit Blanche. The two events do not radically alter thecity in the same way.
100 000

y = 6,318x + 1238,1
R² = 0,8342

50 0000

100 000-50 000

50 000-100 0000-15 000 -10 000-5 0000

5 000

10 000

15 000Figure 5. Correlation between fluctuations.
-50 000-100 000
00:00 05:00 10:00 15:00 20:00 01:00 06:00 11:00 16:00 21:00
Figure 4. The net anomalous paths.
Fête de la Musique (blue) and Nuit Blanche (green).

Fête de la Musique quickly and substantially upsets thenormal order in the city because from the morning onwards
and throughout Saturday day anomalous fluctuations accountfor one third of normal fluctuations. The size of the event
requires organisation in terms of concert venues. The first
concerts, aimed mainly at young people and families, begin
in the early afternoon.
While the standard Saturday peaks between 7.15 and7.29pm, the Saturday of Fête de la Musique peaks much

The conclusion which emerges, quite simply, is that themusical event is a more popular event while the artistic event
is more elitist.
Urban attraction and repulsion
The above analysis does not fully reflect the impact of
the two events on the normal city, because it only takes into
account net fluctuations. We thus distinguish positivefluctuations from negative fluctuations. The former include
the urban nodes and edges which attracted a large number ofspectators during the event. Conversely, the latter show thatsome nodes and edges lost users by comparison with a more
standard weekend. By comparing these two forms ofabnormal fluctuations we identify the urban nodes and edges
which attracted and repelled spectators.

3

Book of abstracts for NetMob 2010

64

MobNet 2010 Proposal: PARIS BY NIGHT

Figure 7 shows these fluctuations for Fête de laMusique. The previous trends do not change, but the figure
shows us that during the day, some concerts attracted anumber of spectators to the detriment of otherneighbourhoods. On the other hand, at the peak of Fête de laMusique, in other words during the evening and the night,
the concerts attracted increasing numbers of spectators
without emptying neighbourhoods. Finally, Sunday suggeststhat no neighbourhood benefited from Fête de la Musique:on the contrary they experienced much lower activity thannormal.

individuals. However, these venues are railway stations andother stations, so it is more difficult to draw conclusions.
25 000
20 000
15 000
10 000120 000

5 000

100 000

0
00:00 05:15 10:30 15:45 21:00 02:15 07:30 12:45 18:00 23:15
Positive (line) and negative (dotted) fluctuations.

80 00060 00040 000
20 0000
00:00 04:45 09:30 14:15 19:00 23:45 04:30 09:15 14:00 18:45 23:30
Positive (line) and negative (dotted) fluctuations.

Positive fluctuations : Saturday, 10:45pm.
Figure 8. Nuit Blanche.

In conclusion, the data shows that the two events
substantially alter urban habits.
Detecting cultural scenes
Positive fluctuations : Saturday, 10:45pm.
Figure 7. Fête de la Musique.

Figure 8 shows these fluctuations for Nuit Blanche. The
previous trends are confirmed again, but there are differenceswith Fête de la Musique. During Saturday daytime, null net
fluctuations are caused by the attraction of some venues
being offset by the repellency of others. At the peak of Nuit
Blanche (Saturday evening and Sunday night), we see thesame relationship as for Fête de la Musique: the arts venues
attract many spectators but this is not to the detriment ofother neighbourhoods. Finally, on Sunday a similar trend
emerges, even if some events venues attract moreIn the section describing the specificities of the two
events (not in this abstract), we suggested the similarity
between a cultural scene within the mobile network and acommunity within a social network. We present the detection
algorithm chosen for this study.
The edge betweenness
In network analysis there are various methods ofdetecting communities [15]: proximity within communities
vs. distance between communities, where proximity anddistance criteria depend on the context being studied. Two
major characteristics suited to our study emerge: on the one
hand, the need to focus on edges in order to take account of
the mobility between the various small events in eachfestival; and on the other hand, the aim of starting with the

4Book of abstracts for NetMob 2010

65

MobNet 2010 Proposal: PARIS BY NIGHT

city as a whole to determine scenes, rather than starting withnodes and edges and aggregating them to determine scenes.
For this reason, the algorithm developed by Newman andGirvan [16-18], often used in network analysis, seemedcomparatively relevant.
This algorithm is founded on the betweenness of edges
rather than nodes. The betweenness indicator measures thenumber of paths between all the pairs of nodes in the
network running along an edge in the network. With a spatial
network, we can therefore take into consideration traffic
flows in a transport network [19], and paths in our radiomobile network. A high value thus represents an edge
responsible for a connection between nodes, and byextension between communities. It is similar to the idea of
weak ties which link two communities vs. strong ties which
define the communities [20]. Granovetter’s urban adaptation
is used in Jane Jacobs’ analyses [21].
The algorithm
The algorithm is founded on the usual measurement of
betweenness in a network. Rather than taking account of all
the paths running along an edge, it is based on the shortest
path. The first step thus involves finding the shortest path
between all the pairs of nodes in the network. In order totake account of the spatial component of the mobile network,
the shortest path is determined using the A* algorithm: inthis way we consider the distance between the nodes. This
gives us the number of geographically shortest paths runningalong each edge in the network, SP*.
The second step consists in taking account of the factthat the network is valued. The idea developed by Newman
and Girvan is to convert the value of an edge into a multiedge network: each edge with a value equal to AP becomes
AP single valued edges. We adapt the analysis to take into
account the fact that we also have valued nodes. We simply
proportionally distribute the value of each node to its edges.
This gives us the number of single paths for each edge in the
network: AP*.
By combining the two steps we can identify, at a given
moment, the edge with the highest score, in other words theedge which connects the most different urban scenes. The
measure is as follows:

SP *ij (T )AP *ij (T ),i ≠ jIllustration: Nuit Blanche
We will illustrate the relevance of our approach using
the example of Nuit Blanche. This event takes place in 70
well-defined venues, dispersed across the city, and linked
together by the metro. Superposing the scenes and thedifferent festival venues gives a very clear picture. The
resulting partitioning is comparatively more accurate thanthat proposed by the official programme (four major scenes).
It takes into account spectators’ actual usages. It also allows
us to determine relative audiences. A more detailed analysis
is performed in the article.

How does music drive Paris?
The same analysis is performed for Fête de la Musique.
The 557 official venues for this festival do not take accountof times and musical genres. It will be expanded upon in thefull article, but because of a lack of space we cannot go into
it any further in this abstract.
References[1][2]

The Economist, February 27th - March 5th 2010.
N.Nova, Les médias géolocalisés: Comprendre les nouveaux médias
numériques, Paris: FYP Editions, 2009.
[3] C.Ratti, R.M.Pulselli, S.Williams, D.Frenchman, “Mobile
landscapes”, Environment and Planning B, p.727-748, 2006.
[4] C.Ratti, A.Sevtsuk, S.Huang, R.Pailer, Mobile landscapes: Graz in realtime, Proceedings of the 3rd Symposium on LBS and
TeleCartography, Vienna, 2005.
[5] F.Calabrese, C.Ratti, Real time Rome, Networks and Communication
Studies 20, 2007.
[6] F.M.Rojas, C.Celdesi Valeri, K.Kloecki, C.Ratti, New York talkexchange, SA+P Press, 2009.
[7] M.C.Gonzalez, C.A.Hidalgo, A.L.Barabasi, “Undestanding individual
human mobility patterns”, Nature 453, 2008.
[8] C.Song, Z.Qu, N.Blumm, A.L.Barabasi, Limits of predictability inhuman mobility, Science, vol.327, 2010.
[9] R.Lambiotte, V.D.Blondel, C.de Kerchove, E.Huens, C.Prieur,
Z.Smoreda, P.Van Dooren, “Geographical dispersal of mobile
communication networks”, Physica A, 2008.
[10] F.Calabrese, J.Reades, C.Ratti, “ Eigenplaces:analyzing cities using
space-time structure of the mobile phone network”, Environment andPlanning B, 2007.
[11] F.Girardin, A.Vaccari, A.Gerber, A.Biderman, C.Ratti, “Quantifying
urban attractiveness from the distribution and density of digital
footprints”, International Journal of Spatial Data Infrastructures
Research.
[12] G.Voronoi, Nouvelles applications des paramètres continues à lathéorie des formes quadratiques, Journal für die Reine undAngewandte Mathematik, vol.133, p.97-178, 1907.
[13] P.E.Hart, N.J.Nilsson, B.Raphael, “A formal basis for the heuristic
determination of minimum cost paths”, IEEE Transactions on Systems
Science and Cybernetics, vol. 4 , p. 100–107, 1968.
[14] J.Candia, M.C.Gonzalez, P.Wang, T.Schoenharl, G.Madey,
A.L.Barabasi, “Uncovering individual and collective human dynamics
from mobile phone records”, Journal of Physics A: Mathematical andTheoretical, vol. 41, 224015, 2008.
[15] S.Wasserman, K.Faust, Social networks analysis: methods andapplications, New-York: Cambridge University Press, 1994.
[16] M.E.J. Newman, M.Girvan, Mixing patterns and community structure
in networks, in Pastor-Satorras R., Rubi J-M., Diaz-Guilera A.,
Statistical Mechanics of Complex Networks, Springer, berlin, 66-87,
2003.
[17] M.E.J. Newman, M.Girvan, Finding and evaluating community
structure in networks, Physical Review E69, 2004.
[18] M.E.J. Newman., Analysis of weighted networks, Physical Review
E70, 2004.
[19] M.T.Gastner, Traffic flow in a spatial network model, Proceedings of
the 6th International Conference on Complex Systems, 2006.
[20] M.Granovetter, “The strength of weak ties”, American Journal of
SOciology 78, p.1360-1380, 1973.
[21] J.Jacobs, The death and life of great American cities, New-York:
Random House, 1961.

5

Book of abstracts for NetMob 201066

Session D

Book of abstracts for NetMob 201067

Book of abstracts for NetMob 2010

68

The “Friends and Family” Mobile Phone Study:
Overview and Initial Report
Nadav Aharony, Cory Ip, Wei Pan, Alex (Sandy) Pentland
MIT Media Lab
Contact: {nadav, coryip, panwei, pendland}@media.mit.edu

Abstract
In this talk we will give an overview of the “Friends and Family” study – a long term
mobile phone experiment, in which a graduate family community is transformed into aliving-lab for investigating a broad range of issues, including individual and group
identity, real world decision making, social diffusion, social health, and privacy
boundaries. In the first phase of the study, starting March 2010, a 100 Android based
phones are distributed to selected participants in the community, equipped with oursoftware platform that turns them into flexible social sensors and intervention-delivery
mechanisms. By the time of the conference we should be able to also present somepreliminary results.

Introduction

Today’s mobile phones are becoming powerful computing and sensing platforms.
We are investigating ways to help people make use of the knowledge collected bytheir own mobile phones, as well as aggregate data contributed by many users, toimprove their lives in constructive ways. In addition, we are investigating how thisdata can contribute to the understanding of societal and community related issues.
In recent years our lab has developed the methodology of Reality Mining, which isdefined as the collection and analysis of machine‐sensed environmental data
pertaining to human social behavior, and is a key component in the transformationof traditional social science into the emerging area of computational social science.
To gather this information, we use both our own home‐brewed sensor platforms aswell as smart‐phones. We have already performed two large‐scale experiments
using close to a hundred phones at MIT campus in recent years. One study was
performed in 2005 with participants from the MIT Media Lab and the Sloan Schoolof Management. The second study was performed at an MIT undergraduate dorm
during the 2008‐2009 academic year. The first study was within a population ofcolleagues and co‐workers. The second was done with a typical undergraduate
population.
Our current goal is to pick a more “realistic” living community, with a population of
couples and families that also have a community life and social interactions with one
another. This community is a graduate family housing community at MIT, which has
more than 400 residents. We would like to equip as many of these residents as weBook of abstracts for NetMob 201069

can with Android smart‐phones running our software platform for data collection
and other study related applications. To begin with, we are starting with handingout approximately 100 Android OS phones to selected residents.
The broad goal for this experiment is to develop mathematical models of social
behavior of individuals and groups. These include (1) models of real‐world groupdynamics (in contrast to group dynamics within organizations and other structured
settings), and also (2) models of the way that different “things” diffuse through asocial network. “Things” can refer to a broad range – it would include the spread of
behaviors, attitudes, and opinions ‐ like exercise habits, smoking habits, musictastes, or political opinions. This also includes the spread of disease like thecommon cold or the flu. It is likely that many of these spread through social
interaction – like social influence of one person on another, or the mere physicalproximity between two people. The models we develop through this study would bethen used to enhance mobile applications and software programs with the ability tocomprehend human social interactions, and consequently, create more relevant,immersive, and privacy aware experience for the users.

Research Methodology
In the Friends and Family study, we are using mobile phones as in‐situ social
sensors to map users’ activity features, proximity networks, media consumption andbehavior diffusion patterns. The phones are augmented with social software toperiodically execute different “probes” that capture information like cell tower ids,
wireless LAN (WLAN) ids, Bluetooth ids, accelerometer and compass data, call and
SMS, statistics on installed phone application and media files and usage andbackground noise/audio features. All phone numbers as well as any open text fields
are encrypted using a one‐way hash function.
The study involved the following data collection components:
1. Data collection by the mobile phone.
2. Surveys to establish “ground truth”.
3. Establish participant spending patterns through purchase receipts.
4. Opt‐in component: Facebook application, which, analogously to the phone
probes, will collect data about the participant’s online social activity.
The first part of the study (approx. 30‐60 days), which is currently launching, is abaseline phase, where data is collected but no feedback will be presented to theusers. After this phase, we begin a series of intervention phases. A simple
intervention would be exposing participants to some of the data that has beencollected through their device, and observing the effect on their behavior. For
example, the participant will be able to review the amount of their social activity, or
information about their approximate sleep hours (which might be inferred using
data from the phone's accelerometer and/or information from an alarm clock
application). Not all users will necessarily be exposed to the same information or
information visualization to allow comparison. Another example intervention is toBook of abstracts for NetMob 201070

allow participants to decide whether to share this information with people in theircontact list. Such feedback will help us investigate the effects of being exposed to
one's own data, as well as to explore privacy issues related to the sharing of thisinformation. Participants might also be exposed to aggregate information. For
example, informing them on what "people like you" are doing, or what "people you
spend time with" are doing. Such feedback must be carefully aggregated andanonymized so that it is not possible to infer information about specific participants.

Research Questions
The research questions we are trying to answer include a wide range of topics. Hereare some examples of different questions that we expect to be able to answer
through our study:•

In the context of individuals: How can the sensed real‐world behavioral
data be used to construct a “rich identity” profile of the user, which is moredetailed and dynamic than current static demographic profiles. How is media
propagation related to the user's face‐to‐face social network? Do social
connectors play a major role? How is social influence defined in this context?
Are there predictive patterns in how users consume and share media orother purchase recommendations? Can mobile devices automatically infer
the user’s interest clusters and social groups, as well as recommend desired
privacy settings based on these patterns?

•

Groups within a community: What can we learn about group dynamics
through the data collected by the experiment? Can we infer which formal andinformal social groups (ethnic, religious, shared hobbies, neighbors, parentsof similar aged children, etc.) participants belong to, and which of these havemore influence in different contexts? How can we use the phones and phonedata to improve community operation? (An example of an idea to improve
community operation would be an application showing when different
common areas are occupied.)•

Community health and wellness: How can we use the phones and phonedata to improve community health and wellness? (An example of data thatcan be collected to improve health and wellness would be flu propagation. An
example of an idea to improve community wellness would be an app to let
people know about exercise habits within the community.)•

Questions related to privacy and data interaction: We want to use thisexperiment as a platform to learn how to deal with the sensitivities ofcollecting and using this deeply personal data. For example we would like toexplore different techniques and methodologies to protect the users’ privacy
while being able to generate meaningful outputs of the system. We would
also like to explore different user interfaces for privacy settings, and forvisualizing this personal data to the user.

Book of abstracts for NetMob 201071

Efficient Collaborative Application Monitoring
Scheme for Mobile Networks
Yaniv Altshuler

Shlomi Dolev

Yuval Elovici

Nadav Aharony

Deutsche Telekom Labs
Computer Science Department Deutsche Telekom LabsMedia LabBen Gurion University, Israel Ben Gurion University, Israel Ben Gurion University, Israel MIT, Cambridge, MA, USA
Email: yanival@cs.technion.ac.il Email: dolev@cs.bgu.ac.il
Email: elovici@bgu.ac.il Email: nadav@media.mit.edu

I. I NTRODUCTION
In this work we discuss the problem of collaborative monitoring of mobile phones applications that are suspected ofbeing malicious. New operating systems for mobile devices
allow their users to download millions of new applications
created by a great number of individual programmers andcompanies, some of which may be malicious or flawed. The
importance of defense mechanisms against an epidemic spreadof malicious applications in mobile networks was recently
demonstrated by Wang et. al [19]. In many cases, in orderto detect that an application is malicious, monitoring its
operation in a real environment for a significant period oftime is required. Mobile devices have limited computationand power resources and thus can monitor only a limited
number of applications that the user downloads. We propose
an efficient collaborative application monitoring algorithm,
harnessing the collective resources of many mobile devices.
Mobile devices activating this algorithm periodically monitor
mobile applications, derive conclusion concerning their maliciousness, and report their conclusions to a small numberof other mobile devices. Each mobile device that receives amessage (conclusion) propagates it to one additional mobile
device. Each message has a predefined TTL. The algorithm’s
performance is analyzed and its time and messages complexity
are shown to be significantly lower compared to existing stateof the art information propagation algorithms. In addition, we
analytically prove that the algorithm is tolerant to Byzantine
attacks aimed for injecting false information into the system.
The algorithm was also implemented and tested extensively ina simulated environment.
II. S COPE AND PARADIGM
Companies that are distributing new mobile devices operating systems had created a market place that motivates
individuals and other companies to introduce new applications(such as Apple’s App Store Google’s Android Market, Nokia’s
Ovi Store and others). The content of the marketplace is notverified by the marketplace operators and thus there is no
guarantee that the marketplace does not contain malicious orseverely flawed applications. Downloading a malicious application from the marketplace is not the only way that a mobile
device may be infected by malicious code. This may also
happen as a result of a malicious code that manages to exploit

a vulnerability in the operating systems and applications or
through one of the mobile phone communication channels
such as Bluetooth, Wi-Fi, etc’ [8], [19].
In many cases, in order to detect that an application ismalicious, monitoring its operation in a real environment fora significant period of time is required. The monitored data is
being processed using advanced algorithms in order to assess
the maliciousness of the application [7], [10], [11].
Harnessing their collective resources, a large group oflimited devices can be shown to achieve a decentralized andefficient information propagation capability. Using such a
service, participating users could significantly improve their“defense utilization” — the ratio between the resources a user
is required to allocate for the collaborative service, and theprobability to block attack attempts.
We present a collaborative application monitoring algorithm
that provides high efficiency, scalability and robustness. The
algorithm is completely decentralized and no supervisingauthority is assumed, nor do any central of hierarchical tasks
allocation or any kind of shared memory. Specifically, we showthat by sending O(ln n) messages, the number of applications
a device would have to monitor in order to become “vaccinated” is reduced by a factor of O(ln n). Using real-world
numbers, implemented as a service executed by 1,000,000
units, assuming 10,000 new applications are released every
month, we analytically show that by monitoring a single
application each month and sending 4 SMS messages per day,a participating mobile device can be guaranteed to be immune
for 99% of all malicious applications.
III. R ELATED W ORK
Since the problem of finding the minimum energy transmission scheme for broadcasting a set of messages in a given network is known to be NP-Complete [1], flooding optimization
often relies on approximation algorithms. For example, in [6],[14] messages are forwarded according to a set of predefinedprobabilistic rules, whereas in [13] a deterministic algorithm
which approximates the connected dominating set within a
two-hop neighborhood of each node is proposed.
In this work we applied a different approach — insteadof a probabilistic forwarding of messages, we assign a TTL
value for each message, using which we are able to guidethe flooding process. The analysis of the system is done byBook of abstracts for NetMob 2010

72

2

TPP
using G(n, p) overlay
Flooding
Network Coded Flooding[3] using G(n, p) overlay
Neighborhood Epidemics[4] using G(n, p) overlay
Hierarchical Epidemics[16] using α-tree overlay
LRTA* [9] in planar
degree bounded graphs
SWEEP [18]in the Z2 grid

Time
(
)
O lnζnin most cases O(ln n)
O (Graph’s diameter))(
O n−1 · p−2

MessagesO(nc )
for some constant cO(c · n)for a constant cO(α · n ln n)branching factor αO(ln n)O (n ln n)

TPP

O(|E|)

Flooding
Network Coded Flooding

O (n)O(n2 )O(n2 )

O(n1.5 )O(n1.5 )TABLE IP ERFORMANCE COMPARISON BETWEEN THE TPP ALGORITHM AND
AVAILABLE STATE OF THE ART ALGORITHMS .

modeling the messages as agents practicing random walk in arandom graph overlay of the network.
It is well known that the basic flooding algorithm, assuming
a single source of information, guarantees completion in aworse case cost of O(n2 ) messages and time equals to thegraph’s diameter, which in the case of a random graph G(n, p)
is approximately O(log n) [2]. Variants of flooding algorithms
use various methods to improve the efficiency of the basic
algorithm, such as area based methods [12] or neighborhood
knowledge methods [15]. An extremely efficient flooding
algorithms in terms of completion time, is the network coded
flooding algorithm, discussed in [3]. In this work, a messagekis forwarded by any receiving vertex d(v)times, while k
is a parameter which depends on the network’s topology.
Using this method, the algorithm achieves a completion timen3
of approximately O( |E|
2 ). This algorithm, however, is still
outperformed by our proposed algorithm. Specifically, ouralgorithm performs(√ n ) faster in graphs with average degree ofless than O
ln n .
An alternative approach to be mentioned in this scope isthe use of epidemic algorithms [17]. There exist a variety of
epidemic algorithms, starting with the basic epidemic protocol[5], through neighborhood epidemics [4] and up to hierarchical epidemics [16]. In general, all the various epidemic variants
has a trade-off between number of messages sent, completiontime, and previous knowledge required for the protocols.
Tables I and II present a summary of the performance of
the TPP algorithm compared to the main body of works inthis domain. The results of the second table assume that the
average degree of network vertices is relatively small, marking
the algorithm which guarantees best performance in gray. The
value of the constant ζ can be approximated as ζ = Ω(ln2 n)
for most real world networks.

IV. E XPERIMENTAL R ESULTS
In order to examine its performance, we have implemented
the algorithm and conducted extensive simulations using various scenarios. In this section we describe one example, due
to space considerations. This example concerns a network of

Neighborhood Epidemics
Hierarchical Epidemics
using α-tree overlay

Time
(
)
O lnζnin most cases O(ln n)
O (ln
)
( n)
O n−1 · p−2cO(n )for some constant cO(ln n)Messages
O (n ln n)O(n2 p)O (n)O(c · n)for a constant cO(α · n ln n)branching factor α

TABLE IIP ERFORMANCE COMPARISON FOR RANDOM G(n, p) GRAPHS , WITH
p < O((n ln n)−0.5 ).

n = 1000 units, having access to N = 100 applications, oneof which was malicious1 . Each unit is assumed to download 30
random applications, monitoring 1 application every week, andallowed to send notification messages to 10 random network
members. Upon completion, at least 990 network members
are required to become aware of the malicious application,and that this would hold in probability of 0.999. In addition,
we assumed that among the network members there are 100
adversaries, whose goal is to mislead at least 50 of the
network’s members to believe that some benign application
is malicious.
Figure 1 shows the time (in days) and messages required inorder to complete this mission, as a function of the decisionthreshold ρ2 . We can see that whereas the adversaries succeed
in probability 1 for ρ < 3, they fail in probability 1 forany ρ ≥ 3. Note the extremely efficient performance of thealgorithm, with completion time of ∼ 260 days using only 5
messages and at most 30 monitored applications per user. The
same scenario would have resulted in 100 messages per user
using the conventional flooding algorithm, or alternatively, in
700 days and 100 monitored applications per user using a
non-collaborative scheme. Figure 2 demonstrates the decreasein completion time and messages requirement as a result of
decreasing the penetration threshold, namely — the portionof the network which we allow to be deceived by attackers. A
similar example concerning the effect of changing the graph’s
density (namely — the number of messages sent by each
unit, upon the identification of a malicious application) is
given in Figure 3. Figure 4 demonstrates the evolution in themalicious application’s penetration probability throughout thevaccination process.
R EFERENCES[1] M. Cagalj, J.P. Hubaux, and C. Enz, Minimum-energy broadcast in allwireless networks: Np-completness and distribution issues, MOBICOM,
2002.
[2] F. Chung and L. Lu, The diameter of sparse random graphs, Advancesin Applied Mathematics 26 (2001), 257–279.
1 Note that the number of malicious applications does not influence thecompletion time of algorithm, as monitoring and notification is done inparallel. The number of message, however, grows linearly with the numberof malicious applications.
2 An application is considered “malicious” where at least ρ messages arereceived concerning its maliciousness from different sources. This mechanism
was designed in order to prevent the injection of false information to the
network

Book of abstracts for NetMob 201073

3

Fig. 1. An experimental result of a network of n = 1000 members, with
N = 100 applications, penetration threshold = 0.01, graph density = 0.01
and 100 adversaries that try to mislead at least 5% of the network into
believing that some benign application is malicious. Notice how changes in ρ
dramatically effect the adversaries’ success probability, with almost no effecton the completion time.

Fig. 2. The effect of decreasing the penetration threshold on the algorithm’scompletion time and number of messages (ρ = 1).

[3] S. Crisostomo, J. Barros, and C. Bettstetter, Flooding the network:
Multipoint relays versus network coding, 4th IEEE Intl. Conference on
Circuits and Systems for Communications (ICCSC), 2008, pp. 119–124.
[4] D. Ganesa, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and
S. Wicker, An empirical study of epidemic algorithms in large scale
multihop wireless networks — technical report ucla/csd-tr 02-0013,
Technical report, UCLA Computer Science, 2002.
[5] R. Golding, D. Long, and J. Wilkes, The refdbms distributed bibliographic database system, In Proc. of Usenix94, 1994, pp. 47–62.
[6] Z. Haas, J. Halpern, and L. Li, Gossip-based ad-hoc routing, IEEE/ACM
Transactions of networks 14 (2006), no. 3, 479–491.
[7] Hahnsang Kim, Joshua Smith, and Kang G. Shin, Detecting energygreedy anomalies and mobile malware variants, MobiSys ’08: Proceeding of the 6th international conference on Mobile systems, applications,and services (New York, NY, USA), ACM, 2008, pp. 239–252.
[8] J. Kleinberg, The wireless epidemic, Nature 449 (2007), 287–288.
[9] R. Korf, Real-time heuristic search, Artificial Intelligence 42 (1990),
189–211.
[10] R. Moskovitch, I. Gus, S. Pluderman, D. Stopel, C. Glezer, Y. Shahar,and Y. Elovici, Detection of unknown computer worms activity based oncomputer behavior using data mining, CISDA 2007. IEEE Symposiumon Computational Intelligence in Security and Defense Applications,
2007, pp. 169–177.
[11] R. Moskovitch, S. Pluderman, I. Gus, D. Stopel, C. Feher, Y. Parmet,
Y. Shahar, and Y. Elovici, Host based intrusion detection using machine learning, 2007 IEEE Intelligence and Security Informatics, 2007,
pp. 107–114.
[12] S. Ni, Y. Tseng, Y. Chen, and J. Sheu, The broadcast storm problem in a
mobile ad hoc network, In Proceedings of the ACM/IEEE International
Conference on Mobile Computing and Networking (MOBICOM), 1999,
pp. 151–162.
[13] L.V.A. Qayyum and A. Laouiti, Multipoint relaying for flooding broadcast messages in mobile wireless networks, Proceedings of HICSS, 2002.
[14] Y. Sasson, D. Cavin, and A. Schiper, Probabilistic broadcas for flooding
in wireless mobile ad-hoc networks, Proceedings of IEEE Wirelesscommunication and networks (WCNC), 2003.
[15] Ivan Stojmenovic, Mahtab Seddigh, and Jovisa Zunic, Dominating sets
and neighbor elimination-based broadcasting algorithms in wirelessnetworks, IEEE Transactions on Parallel and Distributed Systems 13(2002), no. 1, 14–25.
[16] R. van Renesse and K. Birman, Scalable management and data mining
using astrolabe, In Proc. of the First International Workshop on Peerto-Peer Systems (IPTPS02), 2002.
[17] Werner Vogels, Robbert van Renesse, and Ken Birman, The power of
epidemics: robust communication for large-scale distributed systems,
SIGCOMM Comput. Commun. Rev. 33 (2003), no. 1, 131–135.
[18] I.A. Wagner, Y. Altshuler, V. Yanovski, and A.M. Bruckstein, Cooperative cleaners: A study in ant robotics, The International Journal of
Robotics Research (IJRR) 27 (2008), no. 1, 127–151.
[19] P. Wang, M.C. Gonzalez, C.A. Hidalgo, and A.L. Barabasi, Understanding the spreading patterns of mobile phone viruses, Science 324 (2009),
1071–1075.

Fig. 3.
The effect of decreasing the graph density on the algorithm’scompletion time and number of messages (ρ = 1).
1

1
Rho = 20
Penetration probability

Penetration probability

Rho = 1
0.8
0.6
0.4
0.2
0
0

50

100

150
Time

200

250

0.8
0.6
0.4
0.2
0
0

50

100

150

200
Time

250

300

350

400

Fig. 4. The penetration probability of the malicious application, as a functionof the time, with ρ = 1 (on the left) and ρ = 20 (on the right).

Book of abstracts for NetMob 2010

74

Beyond San Fancisco Cabs :Building a *-lity Mining Dataset∗

Marc-Olivier Killijian

Matthieu Roy

Gilles Trédan

CNRS; LAAS
Univ. Toulouse, France

CNRS; LAAS
Univ. Toulouse, France

TU Berlin
Berlin, Germany

marco.killijian@laas.fr

roy@laas.fr

gilles@net.t-labs.tu-berlin.de

ABSTRACTIn this paper, we report our advances, choices and rst insights in the design of a mobile phone powered data collection platform. We believe that collecting such data is vitalto achieve a better understanding/modeling of several phenomenons related to human activity (e.g. mobility, social
contacts, or terminal failures). However, designing such aplatform raised a lot of questions that we present in thispaper.

node encounters a cooperating peer, the rate at which it getsInternet connectivity, the rate at which it (or any peer) fails,
etc. We had to choose these parameters (and their distribution law) by rule of thumb but de nitely wanted to get
actual and accurate data to backup these estimates. Regarding experimental evaluation, we are building an emulation
platform based on small robots that carry laptops running
the algorithms. At the moment we used prede ned vehicular scenarios but we want the platform to be able to use
proper mobility models.

1.

Mobility and Social Models.

MOTIVATION

Context.
The ubiquity of geo-located devices (mobile/smart-phones,
GPS, etc.) permitted scientists to collect datasets containing mobility information. Mining reality (and mobility) outof these datasets has drawn a lot of attention, for example for studying the spread of viruses [9, 12], for designingsocially-aware network routing protocols [2, 8], and in theraising dynamical networks community. These datasets canalso be used to design models of users behavior [5, 7, 17],
phone usage, etc.

Background.
We are interested in building resilient ubiquitous mobile
systems. To attain this goal, several aspects of these systems need to be investigated, from their formal foundations
to their experimental evaluation. As such, we worked on
distributed [16] and cooperative [10] algorithms for such systems, but also on both analytical [3] and experimental resilience evaluation [11] of mobile systems. One of the major
challenge when modeling a mobile distributed system is toprovide an adequate mobility and connectivity scheme, thatshould represent, as precisely as possible, actual interactions
between human beings. Mobile devices are the rst sensing
devices that are almost coupled with their carrier, allowing
to capture human activity with an unprecedented resolution. This drove us to dig in research on mobility datasets,
to perform experimental and analytical evaluation based on
actual mobility traces.
Indeed, as far as analytical evaluation is concerned, we
needed to use parameters representing the rate at which a

It is worth noticing that the whole mobile systems community struggles with classical random-* mobility models.
They are too far from the application scenarios to be sound.
Recent research works try to tackle this problem (e.g., in[13]). Yet, there is still a need for extending mobility models
with failure models for small devices such as mobile phones.
Indeed, as these devices are mass-produced and carried byusers, they are more prone to failures: they move a lot, arelight, and henceforth are prone to fall; they have a small
battery and are prone to energy depletion; they are used forgaming or multimedia purpose, users install a bunch of applications and henceforth they are prone to software failures.
For all these reasons, an ideal dataset would include information about energy consumption, operating system reboots,
mobility, etc.
To the best of our knowledge, there is no dataset that satis es this speci cation. Most of CRAWDAD1 datasets were
produced in a limited vicinity, either during a conference, oron a campus. Very few available datasets include precise localization data [14], most of them focused on contact traces.
Unfortunately phone operators are not keen to release theirdata and do so to only some lucky few [7, 17]. Furthermore,
there are very few data collection tools available. For example, the software used to build the Reality Mining dataset [4]is not maintained anymore [15]. This drove us to decide tobuild our own platform for collecting mobility, failure andenergy consumption data.

2.

A PLATFORM FOR COLLECTION OF
MOBILITY AND SOCIAL TRACES

Contact author: Matthieu Roy

2.1

Operating System Platform

roy@laas.fr

Recently, mobile phone platforms have drawn a lot of attention from manufacturers and users, mainly due to the∗

Submitted to NetMob 2010.

1

http://crawdad.cs.dartmouth.edu/

Book of abstracts for NetMob 201075

opportunity to embark what has become lightweight computers in everyone's pocket. As such, current mid- to highend phones are now equipped with large screens, GPS, highspeed cellular network access, local wireless network interfaces, and various sensors (accelerometers, magnetometers,etc). As for every computing device, interaction with hardware is done through an operating system, using an API.
The di erent phone manufacturers o er platforms that differ radically in their operating system and API choices. In
this section, we describe the various options available, andexplain which platform we chose and why such a choice.
Indeed, from our point of view, the rationale to choose one
platform instead of another is drawn by two main reasons:• the platform should o er a simple way to access asmuch important parameters on user's activity as possible,• the platform should be desirable for users, so that users
will accept to use the platform as their main phone,and run our software.
Most mid- to high-end phone on the market now provide
a GPS for mobility tracing, at least one wireless network
interface (bluetooth), and a large touchscreen. The di erence between available platforms resides in their operating
system and their development model (API and software distribution model). In our view, the best platform for performing a background collection of various parameters on a largebase of users appeared to us to be the Symbian platform: information for programming is easily available, development
tools are mature, the system is very stable, it can run multiple applications in parallel, and it is actively developed andmaintained.

2.2

Hardware Platform

We want to provide many users with smartphones equippedwith our software. This led us to nd a phone (1) that cansense many parameters (at least GPS, WiFi, bluetooth), (2)that has a good autonomy to support the additional energy
consumption necessary for our logging application, (3) thatis cheap and, last but not least, (4) that is considered desirable for users.
We nally opted for the Nokia 5800 smartphone. Its retailcost is about 230e, which is relatively cheap when considering that it provides all hardware we needed, a GPS chip, alarge (640∗360) touchscreen, an accelerometer, a compass, a
WiFi interface and a bluetooth interface in a small form factor (about 100g). Moreover, this phone is considered a good
one from the users point of view, due to its light weight, its
good camera, its free navigation system and the fact that it
can be used with video conference softwares such as Skype.

2.3

Design: what can be sensed

When designing our application, it appeared that the choiceof the programming language would have an impact on available data that can be sensed. In Java (be it Java Micro
Edition or Java Standard Edition), no platform allows a
program to get access to low-level parameter such as the listof available WiFi interfaces. Thus, we had to use systemoriented API and programming language. Symbian standard interface is a C++ API that gives the programmer
access to most of the capabilities of the phone. In our case,
we listed the following interesting sources of information:• GPS information. Location information is essential
when building a mobility trace. This piece of information will be sampled at xed interval. It can also
generate events when passing near some prede ned interest points.
• WiFi access points, and WiFi usage.
• Cellular information.
• Nearby bluetooth devices.
• Battery level. This should be sampled, and the logging
software should collect power events (charging, battery
warning) when they occur.
• Phone calls.
• Accelerometer. Although this parameter is not per se
related to interactions or mobility, it may be used todetect inactivity.
• Compass.
• Proximity Sensor senses wether the surface of the phone
is close to an object (a pocket, an ear)
• Light Sensor.
• Power consumption related resources: CPU usage, current intensity drawn from the battery.

2.4

Implementation considerations

In our rst implementation, we limited the logging to a
subset of available sources of information, as summarized in
Figure 1:
Information
sourceGPS
WiFi
BluetoothBattery level
Battery events
Phone calls
Reboots

periodicity
periodic
periodic
periodic
periodic
sporadic
sporadic
sporadic

fixed/variablesize
xed
variablevariable
xed
xed
xed
xed

Figure 1: Logged sources of information
There are two reasons why we capture these sources of
information only. First, all above data are needed if wewant to capture user interaction with its environment andwith other users, as well as failure information. Second, due
to security restrictions in the Symbian OS, we would have tocertify our program with Symbian Foundation if we wanted
to log information such as the cell identi er the phone isconnected to, or the signal strength of the 3G/HSDPA.

Logging.
Since the program runs on limited resources, much carehas been taken to have the smallest possible footprint on
the system. The program is divided in two: a graphical userinterface, to start/stop the service and to modify logging
parameters, and the logger application itself.
The graphical user interface is simple, and permits theuser to stop the logging service when he/she wants, modify
the frequency of scan for every data source, and turn onor o the logging for every parameter. A screen capture isshown in Figure 2.
The logger is programmed using one thread only, by using
the concept of Active Objects. Active Objects is a systemmechanism that provides a comprehensive way to perform

Book of abstracts for NetMob 201076

many personal information (localization, users interactions)that could be used to ” de-anonymize” a trace [6].

3.

ANALYSIS AND USE OF COLLECTED
DATAOnce the privacy-preserving database is filled with user
data, it can be used for different tasks: analysis of data
for social networks, resilience evaluation of mobility-aware
algorithms, and privacy preserving analysis of the database.

Social Links Engineering.

Figure 2: GUI for managing logger frequency
multiple tasks using system calls (e.g., reading of systemparameters such as GPS information) within a single threadthat acts as a scheduler. Hence, the resulting program uses
low system resources and optimizes battery usage.
The thread is programmed to scan all parameters shownin Figure 1, and to store all information in a text file. The
chosen data format is a simple human readable line-based
log, that shows for each scanned parameter the time of logging, the type of logging, and the value of the log, as shownin Figure 3.

In the vein of recent work on social links engineering [17][7] [5], we plan to use this database, that contains more information than operators’ mobile phones logs, to derive realistic mobility models. Current mobility models are mostly
random-based and thus do not take into account the factthat devices are carried by humans.
In fact, the database will not only be useful for mobility
modeling but, more generally, will serve as a basis for social links analysis, and particularly to answer the following
questions:
Does there exist social locality?, i.e., when social links
exist between a group of users, do these links imply
a more frequent co-locality in the physical world ?
Such a result would have a strong impact on possible
extensions of current social services (MySpace, Twitter, Facebook) to geo-localized systems. Intuitively,
such locality principle should exist. However, measurements would confirm or infirm this hypothesis, andwould allow to develop models that efficiently capture
this potential locality.
Can we model expected interaction patterns between
users, so that we can build collaborative services thatare based on stable users interactions ?
Are there patterns of interactions between users andthe environment that are more likely to appear thanothers ?

Starting scancurrent parameters#GPS#1#WIFI#1#BATTERY#1#CALL#1#BT#1#
2009-10-2 13:50:39#GPS#+43.59407#+1.46388#+136.49504#+25.50000
2009-10-2 13:50:39#BATTERY#71#EPoweredByBattery
2009-10-2 13:50:39#POWER#BATTERY
2009-10-2 13:50:51#BT#berimbau#00:02:26:60:08:8b
2009-10-2 13:50:57#BT#euclide#00:01:14:45:51:1d
Replying to these questions seems for us a prerequisite to
2009-10-2 13:50:58#BT#Nokia marco#00:02:24:40:04:4d
be able to design efficient and useful services for distributed
2009-10-2 13:51:23#BT#Mattmobile#00:02:21:1f:fc:c3
2009-10-2 13:51:32#BT##00:02:25:50:00:0c
systems of mobile users.
2009-10-2 13:51:39#WIFI#Network 1#60#open#Infrastructure#\
00:23:33:78:7f:60#laas-welcome
Resilience evaluation.
2009-10-2 13:51:39#WIFI#Network 2#91#open#Infrastructure#\
Collected data will also serve as an input both for our re00:25:45:b5:75:00#laas-welcome

Figure 3: Example of log

Gathering.
The program that runs on the mobile stores information
locally. We are currently developing a networking part, thatwill opportunistically send logs to a secured server in thelaboratory. Although sending information to a server seems
a simple task, this requires additional work, due to security
risks put on users, particularly for privacy reasons. We areinvestigating cryptographic mechanisms that would protect
users’ privacy, while still permitting analysis on gathered
data.
Obviously, we cannot just anonymize every data tracewith a fixed random identifier, because each trace contains

search on analytical evaluation of resiliency of algorithms [3]and for our reduced-size experimental platform [11]. For analytical evaluation, we will compute probabilistic laws for
useful evaluation parameters, such as the expected time ofusers interaction, the expected time between failures, etc.
For experimental evaluation, we are interested in isolating
mobility patterns that will then be used as an input to ourexperimental platforms, with the final goal of performing
controlled and realistic experimentation by testing different
algorithms on the same mobility patterns, a task that is
impossible in a real environment.

Privacy evaluation.
The last use of the collected data we foresee in the actual
evaluation its privacy-preserving features. From the very
start of the project, we were struggled by privacy issues.
Research results [6] [1] show that simple privacy-preserving

Book of abstracts for NetMob 201077

strategies do not su ce to protect users, due to the hugeamount of personal identifying data traces stored.
The more traces collected, the higher the threat on users'
privacy. As technology evolves, eventually almost everyone will be able to dig into such information, and providing
users with means to protect their data will become a priority. Performing attacks on such a database will permit
us to detect wether our strategies for pseudonymation andprivacy-guarantee is robust.

4.

CONCLUSION

We presented the design and implementation of a mobile
phone powered data collection platform. Our platform collects data that, we believe, will ease the understanding andmodeling of several phenomenons related to human activity:
social links, mobility, etc.
We still have to de ne the economical nature of data collection. Users hardly want to have their privacy exposed
without a counter part. Such reward could consist of several
parts: (1) an economic part, by providing a free terminal,(2) a service-oriented part, by providing services users are
not used to, such as free video-conference service, and, as
we hope, (3) an altruist academical part, providing users
the satisfaction to participate to a research program. It is
worth noticing that the chosen "remuneration scheme" will
imply a bias on collected data that will have to be studied. . .

5.

ACKNOWLEDGEMENTS

The authors would like to thank Hamdi Ayed for its implication in the development of the rst version of the software.

6.

REFERENCES[1] L. Backstrom, C. Dwork, and J. Kleinberg. Wherefore
art thou r3579x?: anonymized social networks, hidden
patterns, and structural steganography. In WWW ’07:
Proceedings of the 16th international conference on
World Wide Web, pages 181{190, New York, NY,
USA, 2007. ACM.
[2] C. Boldrini, M. Conti, and A. Passarella. Social-based
autonomic routing in opportunistic networks, pages
1{37. Springer, 2009.
[3] L. Courtes, O. Hamouda, M. Ka^
aniche, M.-O.
Killijian, and D. Powell. Dependability evaluation ofcooperative backup strategies for mobile devices. In
Proceedings of the IEEE International Symposium on
Pacific Rim Dependable Computing, Melbourne, VA,
Australia, December 2007.
[4] N. Eagle and A. S. Pentland. CRAWDAD data set
mit/reality (v. 2005-07-01). Downloaded fromhttp://crawdad.cs.dartmouth.edu/mit/reality, July
2005.
[5] N. Eagle, A. S. Pentland, and D. Lazer. Inferring
friendship network structure by using mobile phonedata. Proceedings of the National Academy of
Sciences, 106(36):15274{15278, 2009.
[6] S. Gambs, M.-O. Killijian, and M. N. del Prado.
Gepeto: a geo-privacy enhancing toolkit. In Proc. of
the Int. Workshop on Advances in Mobile Computing
and Applications: Security, Privacy and Trust, 24th
IEEE AINA conference, Perth, Australia, April 2010.
IEEE, 2010.

[7] M. C. Gonzalez, C. A. Hidalgo, and A.-L. Barabasi.
Understanding individual human mobility patterns.
Nature, 453(7196):779{782, June 2008.
[8] D. Hay and P. Giaccone. Optimal Routing and
Scheduling for Deterministic Delay Tolerant Networks.
In WONS’09: 6th. Int. Conf. on Wireless On-demand
Network Systems and Services, pages 25{32. IEEE,2009.
[9] M. J. Keeling and L. Danon. Mathematical modellingof infectious diseases. British Medical Bulletin,
92(1):33{42, DEC 2009.
[10] M.-O. Killijian, D. Powell, M. Ban^atre, P. Couderc,
and Y. Roudier. Collaborative backup for dependable
mobile applications. In Proceedings of 2 nd
International Workshop on Middleware for Pervasive
and Ad-Hoc Computing (Middleware 2004), pages
146{149, Toronto, Ontario, Canada, October 2004.
ACM Press.
[11] M.-O. Killijian and M. Roy. A platform forexperimenting with mobile algorithms in a laboratory.
In ACM Conference on Principles of Distributed
Computing (PODC’09), pages 316{317. ACM, 2009.
[12] S. Merler and M. Ajelli. The role of population
heterogeneity and human mobility in the spread of
pandemic in uenza. Proceedings of the Royal Society
B: Biological Sciences, 277(1681):557{565, FEB 22
2010.
[13] M. Musolesi and C. Mascolo. Mobility models for
systems evaluation. In State of the Art on Middleware
for Network Eccentric and Mobile Applications(MINEMA). Springer, February 2009.
[14] M. Piorkowski, N. Sara janovic-Djukic, and
M. Grossglauser. CRAWDAD data set ep /mobility(v. 2009-02-24). Downloaded fromhttp://crawdad.cs.dartmouth.edu/ep /mobility, Feb.
2009.
[15] M. Raento, A. Oulasvirta, R. Petit, and H. Toivonen.
Contextphone: A prototyping platform forcontext-aware mobile applications. IEEE Pervasive
Computing, 4(2):51{59, 2005.
[16] M. Roy, F. Bonnet, L. Querzoni, S. Bonomi, M.-O.
Killijian, and D. Powell. Geo-registers: An abstraction
for spatial-based distributed computing. In Int. Conf.
On Principle of Distributed Systems (OPODIS’08),
volume 5401 of Lecture Notes in Computer Science,
pages 534{537. Springer, 2008.
[17] C. Song, Z. Qu, N. Blumm, and A.-L. Barabasi.
Limits of Predictability in Human Mobility. Science,
327(5968):1018{1021, 2010.

Book of abstracts for NetMob 201078

Mining Large Scale Cell Phone Data
Jean Bolot
SprintBurlingame, California, USA
http://jeanbolot.com/

ABSTRACT
Cell phones are ubiquitous in modern life and the call records
collected by network operators are a powerful tool to study
the behavior of cell phone users, and how those users use network resources, at previously impossible-to-achieve scales.
In this paper we report on results from the analysis of large
scale call records data, and more generally of the data generated by mobile users, at a large cellular operator. We consider in particular three kinds of data, namely social network
data (who calls whom, how often, etc), location and mobility
data (who is where) and spectrum data (who uses how much
spectrum in which cell). We describe practical examples of
insights derived from mining that data, the impact of thedata on areas ranging from marketing to business models or
to security, and also consider interesting research challenges
ahead.

1. INTRODUCTION
The Internet has become a fundamental component ofmodern economies, and it provide services, starting withconnectivity, that are strategic to companies, governments,
families and individual users, and in general to the well functioning of modern life. A growing fraction of those services
are accessed by mobile users. Indeed, the size and strategic importance of the mobile Internet, i.e. the Internet as
accessed via mobile devices such as laptops or cell phones,
is rapidly increasing. Recent reports indicate that the mobile Internet is ramping up in size faster than the ”desktop
Internet” did in the 80’s and 90’s; in fact, the estimated total value of the mobile data industry grew by 20% in 2009
- a year of major economic crisis when the global economy
decreased by 5% - and mobile data revenues reached $284B[5]. This is now larger than the total PC Internet economy,
including Internet content and advertising revenues plus all
subscription fees such as monthly dial up and broadband
access fees. Furthermore, the number of users of the mobile Internet (measured by the number of users accessing
browser-based services on cell phones only) is estimated at

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$5.00.

between 500 million and 1 billion, almost on par with thetotal number of PCs connected to the Internet [5, 1]. Thus,
cell phones already dominate the Internet, and their importance will continue to grow [4].
A key characteristic of cellular networks and devices istheir ability to capture and analyze (at least partial) information on the behavior of mobile users. In particular, operators have routinely captured large scale location data forbilling purposes, but also to improve location management
or satisfy legal requirements such as E911. More recently
they, as well as a number of analytics companies and academic research groups worldwide, have started analyzing a
growing variety of data including social network data (whocalls whom), location and mobility data (where users arewhen they call or use services), click-stream data (which sequence of sites users visit, or which sequence of applications
and services they use), etc.
In this paper, we report on results from the analysis ofsuch data carried out at a large cellular operator. We consider in particular three kinds of data, namely social network
data, location data and spectrum usage data (who uses how
much spectrum in which cell). We describe some of the insights derived from mining that data and consider some of
the interesting research challenges ahead.

2.

SOCIAL NETWORKS

We have analyzed a very large social network gatheredfrom call details records, which reﬂects the voice and SMS
interactions of more than ten million users through hundredsof millions of calls and SMS exchanges. We examined the
distributions of the number of phone calls per customer; thetotal talk minutes per customer; and the distinct number ofcalling partners per customer. We found that these distributions are skewed, and that they signiﬁcantly deviate fromwhat would be expected by conventional wisdom, namely
power-law and lognormal distributions.
We found instead that our observed distributions (number of calls, of distinct partners, and of total talk time)very closely ﬁt a lesser known but more suitable distribution, namely the Double Pareto LogNormal (DPLN) distribution [6]. We found good ﬁts over time (morning-evening,
weekday-weekend) and space (US East Coast-West Coast,urban-suburban).
More importantly, we also found that our graph evolved
over time in a way consistent with a generative process basedon geometric Brownian motion. Furthermore, this generative process lends itself to a natural and appealing social
wealth interpretation, and also allows for extrapolations andBook of abstracts for NetMob 201079

interpolations. We hope that our success with DPLN spurs
further studies involving other datasets and their underlying
generative processes. In particular, we hope that our “social
wealth” interpretation and analysis will serve as an incentive
for social scientists to study the large-scale evolutionary aspects of social characteristics. Indeed, we continue to collectdata from our social network for longer-term analysis.

3. LOCATION AND MOBILITY
We have also analyzed call records to understand the mobility patterns of more than a million users over several thousand square miles. We made two contributions to the analysis of mobility patterns of cell phone users. First, using
only coarse-grained location information, namely the location of the cell tower associated with a user at the beginningand end of each call, we examined the scaling laws of human mobility, in terms of distance and time. We found thatboth the distance traveled as well as the duration of calls(on periods) and pauses (oﬀ periods) are heavy tailed, inagreement with earlier results (e.g. [3]). However, we foundthat mobility patterns change during and in between calls,
and that patterns are correlated over time, with strength ofcorrelation dependent on activity.
Second, we developed a general technique, using tools
from stochastic geometry and Bayesian statistics [7], to reﬁne mobility models as more precise location information
becomes available [11]. Thus, we can correct the distributions of distance traveled and direction as coarse location
information is augmented by information such as distance tothe associated cell tower, signal strength, location of neighboring cells towers, etc. To demonstrate the beneﬁts of ourtechnique, we ﬁrst showed, using timing measurements fromcall records, that users are not uniformly distributed in cells.
We then showed how that location information impacts theestimated distance distribution and then extended our earlier technique, illustrating the impact of increasingly more
precise location information. Our approach is very generaland applicable not just to cellular networks, but to otherwireless networks such as wireless LANs (WiFi, ...) or adhoc networks.

4. SPECTRUM USAGE
Most existing studies of spectrum usage have been performed by actively sensing the energy levels in speciﬁc RF
bands including cellular bands. Our approach has been toprovide a unique, complementary analysis of cellular primary usage by analyzing a dataset collected inside a cellular
network. One of the key aspects of our dataset, comparedto others examined in related spectrum analysis, is its scale- it consists of data collected over three weeks at hundredsof base stations. We dissected this data along diﬀerent dimensions to characterize and model primary usage as well as
understand its temporal and spatial variations. Our analysis
revealed several results that are relevant if Dynamic Spectrum Access (DSA) approaches are to be deployed for cellular frequency bands. For example, we found that call durations show signiﬁcant deviations from the often-used exponential distribution. Though this can complicate the modeling of primary usage, we found that a random walk process,which does not use call durations, can be used for modelingthe aggregate cell capacity. Another novel result we foundis that spatial spectrum usage is highly non-uniform, espe-

cially during periods of high load, with clusters of sectors
whose intra-cluster usage patterns are correlated.
We also considered the more fundamental problem of whether
or not spectrum sensing is actually a viable approach to estimate when and how much secondary users can take advantage of available capacity. Indeed, sensing mechanisms that
estimate the occupancy of wireless spectrum play a cricital role in enabling non-interfering secondary usage. The
problem of designing such mechanisms is, therefore, crucial
to the success of approaches based on Dynamic Spectrum
Access. We developed key insights into this problem by
empirically investigating the design of sensing mechanisms
applied to check the availability of excess capacity in CDMAvoice networks. We focussed on power-based sensing mechanisms since they are arguably the easiest and the mostcost-eﬀective.
We made three main contributions [9]. First, we foundthat accurate single sensor spectrum sensing is essentiallyunachievable, i.e. power at a single sensor is too noisy tohelp us accurately estimate unused capacity. However, we
also found that there are well-deﬁned signatures of call arrival and termination events. Using these signatures, we
showed that we can derive lower bound estimates of unused
capacity that are both useful (non-zero) and conservative(never exceed the true value). Finally, we used a combination of measurement data and analysis to deduce that multiple sensors are likely to be quite eﬀective in eliminating
the inaccuracies of single-sensor estimates.

5.

FUTURE RESEARCH: BUSINESS MODELSThe capture and availability of large scale cell phone data
has enabled, and will continue to enable, a wide range of
new services. For example, in the case of location and mobility data, the capture and availability of such data hasenabled the development of many location-based or locationaware services, and indeed an rapidly increasing numberof such services is now available, ranging from navigation
to location-aware advertising, friend ﬁnder, etc, and many
more are announced or launched on a daily basis. However,this location data, since it enables new services and new
economic activities, is seen as economically valuable. This
raises the question then of how valuable it is, and how toquantify that value. This is precisely the goal of our recent
research.
Using insights from cell phone data, we have developed
an analytic framework, namely models and the techniques
to solve them, to help quantify the economics of location
information [2]. Our aim has been to derive models which
can be used as decision making tools for entities interested
in or involved in the location data economics chain, suchas mobile operators or providers of location aware services(mobile advertising, etc). We considered in particular thefundamental problem of quantifying the value of diﬀerent
granularities of location information, for example how much
more valuable is it to know the GPS location of a mobile user
compared to only knowing the access point, or the cell tower,that the user is associated with. We have used our approachto derive insights into what is arguably the quintessential
location-based service, namely proximity-based advertising.
To our knowledge, our work is the ﬁrst one to present andanalyze economic models which can help understand the eco-Book of abstracts for NetMob 201080

nomic value generated by mobile users with location based
services, for diﬀerent granularities of location informationin wireless networks. We believe that the work provides animportant ﬁrst step towards a general analysis of not justthe data itself, but also of the business models enabled bylarge scale cell phone data.

6. REFERENCES[1] T. Ahonen, Mobile as the 7th Mass Media, London,
UK: futuretext, 2008.
[2] F. Baccelli, J. Bolot, “Modeling the economic value oflocation and preference data of mobile users”,
submitted for publication, Nov. 2009.
[3] M. Gonzalez, C. Hidalgo, and A. Barabasi,“Understanding individual human mobility patterns”,
Nature, vol. 453, pp. 479–482, 2008.
[4] S. Keshav, “Why cell phones will dominate the futureInternet, Computer Communications Review, vol. 35,
no. 2, April 2005.
[5] M. Meeker, The Mobile Internet Report, Chichester:Morgan Stanley, Dec. 2009.
[6] M. Seshadri, S. Machiraju, A. Sridharan, J. Bolot, J.
Leskovec, C. Faloutsos, “Mobile call graphs: Beyond
power-law and lognormal distributions”, Proc. ACM
KDD Conference on Knowledge Discovery and Data
Mining, Las Vegas, Aug 2008.
[7] D. Stoyan, W. Kendall, and J. Mecke, Stochastic
Geometry and its Applications, Wiley, 1995.
[8] D. Willkomm, S. Machiraju, J. Bolot, A. Wolisz,“Primary users in cellular networks: A large-scalemeasurement study”, Proc. IEEE Symp. Dynamic
Spectrum Access Networks (Dyspan), Chicago, IL,
Oct. 2008.
[9] D. Willkomm, S. Machiraju, A. Wolisz, “The problemof spectrum sensing in cellular networks”, submitted
for putblication, Mar 2010.
[10] H. Zang, J. Bolot, “Mining call and mobility data to
improve paging eﬃciency in cellular networks”, Proc.
ACM Mobicom ’07, Montreal, Canada, Sept. 2007.
[11] H. Zang, F. Baccelli, J. Bolot, “Bayesian inference for
localization in cellular networks”, Proc. IEEE Infocom
2010, San Diego, CA, Apr. 2010.

Book of abstracts for NetMob 201081