## Homesick L´ evy walk: A mobility model having Ichi-go Ichi-e and scale-free properties of human encounters

Akihiro Fujihara 1 and Hiroyoshi Miwa 2 1 Department of Management Information Science, Fukui University of Technology, 3-6-1 Gakuen Fukui Fukui 910-8505, JAPAN Email: fujihara@fukui-ut.ac.jp 2 Graduate School of Science and Technology, Kwansei Gakuin Univ. 2-1 Gakuen Sanda Hyogo 669-1337, JAPAN

Email: miwa@kwansei.ac.jp

Abstract -In recent years, mobility models have been reconsidered based on findings by analyzing some big datasets collected by GPS sensors, cellphone call records, and Geotagging. To understand the fundamental statistical properties of the frequency of serendipitous human encounters, we conducted experiments to collect long-term data on human contact using short-range wireless communication devices which many people frequently carry in daily life. By analyzing the data we showed that the majority of human encounters occur once-in-an-experimentalperiod: they are Ichi-go Ichi-e. We also found that the remaining more frequent encounters obey a power-law distribution: they are scale-free. To theoretically find the origin of these properties, we introduced as a minimal human mobility model, Homesick L´ evy walk, where the walker stochastically selects moving long distances as well as L´ evy walk or returning back home. Using numerical simulations and a simple mean-field theory, we offer a theoretical explanation for the properties to validate the mobility model. The proposed model is helpful for evaluating long-term performance of routing protocols in delay tolerant networks and mobile opportunistic networks better since some utilitybased protocols select nodes with frequent encounters for message transfer.

In parallel with the understanding of human mobility patterns, recently, many researchers become actively engaged in studies on mobility models, and many mobility models have been proposed [3], [4]. Traditional mobility models, such as Random Walk (RW), (truncated) L´ evy Walk (LW), Random WayPoint (RWP), are simple and basic: they can easily be used for numerical simulations in general purposes, but they are far from real human mobility patterns. Therefore, newly proposed models have become more realistic and complicated : They includes more parameters to explain many statistical properties on human mobility patterns and social effects, thus they resultingly consume more memory space as simulation time progresses, such as SLAW [5]. The more a model explains, however, the harder it gets to use for the simulations with a large number of walkers in general.

Keywords -Mobility models, Contact frequency, Ichi-go Ichi-e, Power law, and Delay Tolerant Networks.

## I. INTRODUCTION

In recent years, many kinds of human-carried mobile devices, such as smartphones and tablets, that enable many high-tech sensors and wireless communications have been increasingly pervasive throughout the world. Because most of the people in the world usually carry these devices in their lives, their activity logs, such as places where they visit and persons who they are connected with, can be easily recorded using GPS, cellphone call, and Geotagging. We are living in the era of Big data: by analyzing collections of data on people's activity, big companies can take advantage of success in their businesses. Also, academic researchers can investigate human activities and social behaviours in more details than ever. For example, some recent studies based on the analysis of Big data of human mobility patterns have revealed that human behavior is easily predictable because human mobility is biased in general [1], [2]. This result shows that human mobility is far from random, but is ordered.

These mobility models are often used for evaluating performance of routing protocols in Delay Tolerant Networks (DTNs) [19] and Mobile Opportunistic Networks (MON) [6], [7]. To evaluate the performance in systems with a large number of mobile nodes, we need to select a balanced mobility model properly. Because the above routing protocols are often contact-based ones, the model doesn't necessarily preserve real mobility patterns, but it must have real contact patterns. In the context of information communication networks, many researchers frequently mention statistical properties on intercontact time (or inter-meeting time) to select the model. But, we would argue in this paper that statistical properties on contact frequency is also an important factor to properly select the mobility model.

By the way, there is a famous Japanese proverb closely related with the frequency of human contacts which is called Ichi-go Ichi-e . This proverb is literally translated as 'One chance in a lifetime' or more specifically as 'Treasure every encounter, for it will never recur.' This phrase is closely associated with the history of the tea ceremony of Japan. Sen no riky¯ u (1522-1591), the famous tea master during the age of the provincial wars, originally taught this proverb to his pupils in the spirit of good service. Later, at the end of the Edo Period, Ii Naosuke (1815-1860), an accomplished practitioner of the Japanese tea ceremony, rediscovered and reconsidered this lesson as it is known today.

We know from experience that to meet with someone (or something) is sometimes very precious, and we might wonder about how often we have once-in-a-lifetime meetings in our daily lives or whether there is any statistical law that governs our meetings with people (or things). To the best of our knowledge, no scientific study has answered these questions because of the difficulty of collecting long-term data concerning human contact. However, given the recent advances in mobile wireless communication technologies, studies on the statistical physics of serendipitous human encounters can now be undertaken.

Our research group collected data concerning daily human contact using Bluetooth and Wi-Fi wireless communication technologies. Today, billions of electronic devices equipped with Bluetooth and Wi-Fi are used throughout the world. Most of these devices are light and mobile, including mobile PCs and phones, PDAs, tablets, and portable game machines. Therefore, they tend to be carried at almost all times. In addition, the communication range of Bluetooth and Wi-Fi is usually on the order of several meters, which is nearly the same as the range that humans can see when observing those around them. Thus, by scanning and logging nearby Bluetooth and Wi-Fi devices, we can collect reasonably well-sampled data concerning human encounters. In this case, here, encounter should be defined as a state that other humans having the device happen to come close within several dozen of meters at a maximum distance of its communicable range. In our experiment, we used PDAs and smartphones to continuously scan once every twenty seconds and to record pairs of time stamps and MAC addresses of detected devices, which indicated when a participant of the experiment encountered other people. A sample data logging software that our group uses is available as an open-access application for Android OS [8]. To calculate the contact frequency, we need to give a threshold value θ m where two consecutive device detections whose interval time is less than the threshold value are within the same encounter. In this research, we give θ m = 1[ hour ] as a choice, but we also have checked that varying the choice of the threshold from some minutes to some hours is not sensitive for the whole contact frequency. After conducting our experiment, we obtained Long data (rather than a recent buzzword Big data ) whose experimental period is between a minimum of several months and a maximum of more than two years. (See Table I and II). A dozen of people (university teachers, students, and company workers) participated and in total more than 50,000 different devices are detected in the experiment.

In this paper, by analyzing the collected experimental data, we exhibit two basic statistical properties of human contact frequency in the long data of human serendipitous encounters: (1) the property of Ichi-go Ichi-e, under which most human encounters occur once-in-a-experimental-period, and (2) the scale-free property of the remaining more frequent meetings. We can find that these properties clearly emerge for each individual when analyzing the Long Data. Inversely, it is difficult to observe these properties by analyzing shortterm data even if they are categorized into the Big Data. To theoretically explain the origin of these statistical properties observed in the experiment, we furthermore propose 'Homesick L´ evy Walk' as a simple mobility model. This is a minimal stochastic model of human mobility that traces whether the walker stochastically selects moving long distances as well as the L´ evy walk [9], or returning back home as a minimum social effect. In order to validate the mobility model, we offer a theoretical explanation for the properties of human contact using numerical simulations and a simple mean-field theory, which is the main contribution of the paper.

The rest of the paper is organized as follows. In Section II, we show the experimental results of analyzing collected data with Bluetooth and Wi-Fi opportunistic communications. In Section III, we propose a minimal stochastic model of human mobility patterns as a way to simultaneously explain both the two basic statistical properties. In Section IV, we perform numerical simulations to show that the minimal model can explain these properties. Section V demonstrates a simple meanfield theory to explain the emergence of these properties. We summarize our work, discuss future directions, and comment on an application of the model to performance evaluation of routing protocols in Delay Tolerant Networks in Sections VI and VII.

## II. EXPERIMENTAL RESULTS

First, we define R t ( ) as the ratio of one-time meetings to all meetings until time t . The ratio of Ichi-go Ichi-e (once-in-a-lifetime meetings) to all encounters can also be denoted as R t ( ) at t = T where T is the end of life. Some typical time variations in R t ( ) during the experiment are shown in Fig. 1. Although the initial patterns of R t ( ) vary strongly from one individual to the next, all of them stabilize as time progresses. Therefore, we may roughly assume that each of the time variations in R t ( ) converges to some fixed point around the ratio R T ( ) . Under this assumption, we may consider the time-averaged ratio over the experimental period denoted as 〈 R 〉 t to be approximately equivalent to the ratio R T ( ) . We present the time-averaged ratio using Bluetooth, 〈 R bt 〉 t , and Wi-Fi, 〈 R wf 〉 t , in Tables I and II, respectively. Averaged over all participants, the percentages of Ichi-go Ichie meetings using Bluetooth and Wi-Fi are approximately 8090%, meaning that the majority of human encounters occur once-in-an-experimental-period.

We also considered the complementary cumulative distribution function (CCDF) for human contact frequency. As illustrated in Fig. 2, the CCDF clearly follows a power-law distribution,

$$F ( X \geq x ) \equiv \bar { F } ( x ) \sim x ^ { - k }, \text{ \quad \ \ } ( 1 )$$

where k is a scaling exponent. Note that this power law is satisfied only for the remaining 10-20% of encounters, those that occur more than once for each individual. In other words, a large gap exists between x = 1 and x ≥ 2 in ¯ ( F x ) . The estimated scaling exponents of Bluetooth, k bt , and WiFi, k wf , which were determined using the experimental data, are summarized in Tables I and II, respectively. For almost all the participants, the estimated scaling exponents are lower than two. Because of this, the variance of the CCDF tends to diverge during a long experimental period. This divergence indicates that the number of encounters that the participants meet with people in their experimental periods has no characteristic scale. In other words, meetings inherently exhibit extreme inequality, making it difficult to predict how many opportunities are left to encounter someone (or something).

Fig. 1. Time variations in the ratio R t ( ) for individual participants using (a) Bluetooth and (b) Wi-Fi (line with points) and their time-averaged ratios 〈 R 〉 t over the experimental time (solid line). In the legends, those of four participants (E, C, B, and A in Tables I and II) are described.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-b1192e04-6576-4bb4-80e4-ce916d7d4dd4.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-3a546d53-5b96-48b5-89de-a0a1704c602e.jpg)

TABLE I. THE TIME-AVERAGED RATIO OF ICHI-GO ICHI-E 〈 R bf 〉 t AND THE SCALING EXPONENT k bf FOR HUMAN CONTACT FREQUENCY OBTAINED FROM THE BLUETOOTH DATA FOR THE TEN PARTICIPANTS.

| Participant ID   | Experimental period   | 〈 R bt 〉 t    |   k bt |
|------------------|-----------------------|-----------------|--------|
| A                | 2009/03/13-2011/05/31 | 0 . 89 ± 0 . 02 |   1.63 |
| B                | 2009/04/28-2010/12/16 | 0 . 87 ± 0 . 01 |   1.34 |
| C                | 2010/06/10-2011/08/09 | 0 . 90 ± 0 . 01 |   1.42 |
| D                | 2010/09/01-2011/08/08 | 0 . 87 ± 0 . 01 |   1.25 |
| E                | 2010/09/30-2011/08/10 | 0 . 92 ± 0 . 01 |   1.32 |
| F                | 2010/10/18-2011/02/22 | 0 . 93 ± 0 . 01 |   1.24 |
| G                | 2010/10/19-2011/03/09 | 0 . 93 ± 0 . 01 |   1.29 |
| H                | 2010/10/21-2011/01/27 | 0 . 89 ± 0 . 01 |   1.39 |
| I                | 2010/10/21-2011/02/03 | 0 . 87 ± 0 . 02 |   1.17 |
| J                | 2010/11/10-2011/03/31 | 0 . 84 ± 0 . 03 |   2.23 |

## III. HOMESICK L´ EVY WALK

Next, we propose a minimal stochastic model of human mobility patterns as a way to simultaneously explain both the Ichi-go Ichi-e and scale-free properties of human encounters. A number of researchers have recently reported that human mobility traces statistically exhibit the L´vy walk (LW) [10]e [13]. A L´ evy walker in d -dimensional space determines his or

CCDF

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-8d038a67-66c8-42ef-b03e-2829ba15814e.jpg)

0

CCDF

# of Contacts

Fig. 2. CCDF for human contact frequency ¯ ( F x ) using (a) Bluetooth and (b) Wi-Fi (dots). Least squares fitting (LSF) of each CCDF (solid line). In the legends, those of four participants (E, C, B, and A in Tables I and II) are described.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-6337e2ad-ffa2-4387-ad33-bcf1ecad9137.jpg)

TABLE II. THE TIME-AVERAGED ICHI-GO ICHI-E RATIO 〈 R wf 〉 t AND THE SCALING EXPONENT k wf FOR HUMAN CONTACT FREQUENCY OBTAINED FROM THE WI-FI DATA FOR THE TEN PARTICIPANTS.

| Participant ID   | Experimental period   | 〈 R wf 〉 t    |   k wf |
|------------------|-----------------------|-----------------|--------|
| A                | 2009/09/03-2011/05/31 | 0 . 72 ± 0 . 01 |   1.3  |
| B                | 2009/09/01-2010/12/17 | 0 . 65 ± 0 . 02 |   1.27 |
| C                | 2010/06/10-2011/08/09 | 0 . 77 ± 0 . 02 |   1.19 |
| D                | 2010/09/01-2011/08/08 | 0 . 87 ± 0 . 01 |   1.25 |
| E                | 2010/09/30-2011/08/10 | 0 . 81 ± 0 . 02 |   1.28 |
| F                | 2010/10/18-2011/02/22 | 0 . 80 ± 0 . 03 |   0.94 |
| G                | 2010/10/19-2011/03/09 | 0 . 82 ± 0 . 01 |   0.9  |
| H                | 2010/10/21-2011/01/27 | 0 . 73 ± 0 . 02 |   1.4  |
| I                | 2010/10/21-2011/02/03 | 0 . 73 ± 0 . 01 |   1.42 |
| J                | 2010/11/10-2011/03/31 | 0 . 63 ± 0 . 01 |   1.42 |

her destination; the travel distance from the present location l is governed by an independently and identically distributed power-law distribution,

$$p ( l ) \sim l ^ { - ( 1 + \beta ) },$$

where 0 &lt; β ≤ 2 is the L´ evy index. The direction from the present location to the next destination location is usually

Fig. 3. Typical sample traces for L´ evy walk (LW) and homesick L´ evy walk (HLW). The initial position of each walker is indicated by the grey circle, which is assumed to be the hub of activity (or home) in the HLW scenario.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-41ca6ad2-6540-4da3-9498-9b45116d9732.jpg)

determined by the uniform distribution. This feature has been found to be common to the mobility of humans and animals in two-dimensional space [14]-[17].

However, the scale-free property of walk lengths is insufficient to explain the statistical properties of human contact frequency. We numerically confirmed that the CCDF of contact frequency for L´ evy walkers in bounded two-dimensional space generally decays exponentially at the tail. Let us consider what is lacking in the ordinary L´ evy walk scenario. A L´ evy walke r easily travels long distances, but has difficulty returning to his or her original position (refer to Fig. 3). In real life, however, each participant typically frequents his or her own hub of social activity (or his or her own home). This reality strongly determines most of the topology of human mobility traces. Taking into consideration the role of the hub, we propose an extended version of the L´ evy walk named the 'Homesick L´ evy Walk (HLW).' In this model, after arriving at the destination determined by the power-law walk length in Eq. (2), there exists a certain fixed probability α that the L´ evy walker will become homesick and return home; otherwise, according to probability (1 -α ) , the walker will determine his or her next destination using Eq. (2) and continue travelling. By definition, HLW with a homesick probability of α = 0 reduces to LW. For the sake of convenience, we define the initial position of HLW as home. The detailed procedure to move two-dimensional HLW is shown in Motion Control 1. The difference between the sample traces associated with the (simple) L´ evy walk and the homesick L´ evy walk is illustrated in Fig. 3.

In the name of this model, we use the word walk but not flight . In general, walk means that a walker moves with a finite velocity to the destination, but flight means that a walker jump instantly to the destination, which is the difference between these words. Because we also consider serendipitous encounters on the way to the destination, we introduce homesick L´ evy walk here. But, Homesick L´ evy Flight (HLF) can be defined by a similar way with changing from walk to flight in the model.

## IV. NUMERICAL SIMULATIONS

We performed numerical simulations for N homesick L´ evy walkers in a bounded two-dimensional space. Initially, N = 1000 walkers were uniformly distributed within a 1726[ m ] × 1726[ m squared region. The number of the walkers ] N does not change in the simulations. The density of the walk-

## Motion Control 1 : (Two-dimensional) Homesick L´ evy Walk

Require: Initial position: Hub of activity (or home) x home (The current position x now = x home ), Initial state: State == Stop; the homesick probability α ; the scaling exponent of the CCDF of contact frequency β

while TRUE (The walker is alive.) do if

State == Stop then

State == Move if Probability: α then

Destination == Hub of activity ( x dest = x home )

else

New destination x dest = x now + l × ( cos θ , sin θ ), where l is determined by Eq. (2) and the angle θ is given by the uniform distribution on [0 , 2 π ) .

end if

## end if

Start moving to the destination x now ← x now + ∆ l × ( cos θ , sin θ ), where ∆ l is the distance that the walker moves in a single step.

if

x

now

==

x

home or

x

dest then

State == Stop

(The walker may wait for a while.)

end if end while

ers was determined based on the average population density of Japan, approximately 336[ km -2 ] , because all of the study participants live mainly in Japan. The distance between the present position and the next destination described using the polar coordinate l = ( r cos θ, r sin θ ) is randomly generated from the probability distribution function, p l ( ) ≡ p r p θ ( ) ( ) , where

$$\underset { \substack { \text{rere} \\ \text{will} \\ \text{$2$ to} \\ \text{next} \quad \text{end} \quad \text{the} \quad \text{milliseconds} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad\text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end} \quad \text{end},$$

and the minimum travelling distance r m = 1[ m . ] These equations are derived from Eq. (2) to satisfy the normalization condition ∫ ∞ r m p l ( ) dl = 1 . We assumed that for each time-step, all of the walkers move with a constant speed v = 1[ m/s , and ] a small number of walkers meet together if they are within a fixed communication radius c = 1[ m . We also assumed that ] after a walker arrive at a destination, the walker waits a single time-step to determine the next destination.

Next, we considered the effects of the homesick property and long-distance travelling on the time-averaged Ichi-go Ichie ratio 〈 R 〉 t and the scaling exponent of the CCDF of the contact frequency k , varying α and β . The typical time evolution of R t ( ) is illustrated in Fig. 4 (a). As observed in Fig. 1, each R t ( ) tends to converge as time progresses. The time-averaged ratio 〈 R 〉 t , calculated by averaging R t ( ) over the simulation time, is also plotted for the ranges 0 ≤ α &lt; 1 and 0 ≤ β ≤ 1 in Fig. 4 (b). We numerically confirmed that 〈 R 〉 t tends to decrease with increases in α and β . Also, we observe that by roughly tuning parameters α and β to sufficiently small values, we obtain a value of more than 80% for 〈 R 〉 t and the numerical results becomes consistent with the experimental ones.

In Fig. 5(a), we also present some typical CCDFs for contact frequency based on the numerical results. We can clearly

/a0

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-3e3b5da2-ef49-421a-838f-ff85d1274e50.jpg)

✁

✄

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-0ce37466-5593-4995-b67b-9e5d9fe5c4e5.jpg)

☎

✆

Fig. 4. (a) The typical time evolution of R t ( ) in the L´vy walk ( e α = 0 ) and the homesick L´ evy walk ( α &gt; 0 ) determined using numerical simulations for N = 10 3 , T = 2 0 . × 10 [ ] 4 s , α = 0 0 1 0 2 0 3 0 4 , . , . , . , . , and β = 0 1 . (lines with dots). The time-averaged Ichi-go Ichi-e ratios 〈 R 〉 t are also included (solid line). (b) Relationship between 〈 R 〉 t and α and β over the ranges 0 ≤ α &lt; 1 and 0 ≤ β ≤ 1 .

see that the CCDF created using HLW for α &gt; 0 obeys a power-law distribution, whereas that created using LW ( α = 0 ) decays exponentially at the tail, as we mentioned before. This exponential decay for α = 0 was observed for the entire range, 0 ≤ β ≤ 1 . The results indicate that the homesickness component of HLW is essential to the scale-free property of contact frequencies. We also consider the relationship between the scaling exponent k for contact frequency and for α and β calculated using least-squares fitting. As observed in Fig. 5(b), k has a weak decreasing trend with increasing α and β for 0 &lt; α &lt; 1 and 0 ≤ β ≤ 1 . The most important point is that the value of k matches the experimental values of k bt and k wf in Tables I and II when we keep α &gt; ( 0 ) and β small, as shown in Fig. 5(b). As a result, we numerically demonstrate that the HLW stochastic model can explain human contact frequency.

It should be emphasized that the contact frequencies of Homesick Random Walk (HRW) and Homesick Random WayPoint (HRWP) seem to be different from that of HLW as shown

✝

✝

CCDF

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-99b87d83-8884-4bbd-84b4-90e926cd8928.jpg)

✟

Scaling exponent k

Fig. 5. (a) Typical CCDFs for contact frequency values ¯ ( F x ) employing LW and HLW in numerical simulations where N = 10 3 , T = 10 [ ] 5 s , and α = 0 0 1 0 2 0 3 , . , . , . , 0 4 . , β = 0 (dots) with least squares fitting (LSF) for the CCDFs (solid line). (b) Relationship between the estimated scaling exponent k from the CCDFs for contact frequency and α and β for 0 &lt; α &lt; 1 and 0 ≤ β ≤ 1 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-fd547fd4-02d2-40f8-98be-cca7400fca19.jpg)

in Figs. 6 and 7, thus tail's fatness of these distribution is less than that of the power-law distribution.

## V. MEAN-FIELD THEORY

Finally, we use a simple mean-field theory of HLW to explain the emergence of these phenomena. We focus on one walker whose home is fixed at the origin of the twodimensional space, whereas the other walkers are assumed to be spatially fixed and uniformly distributed in the space. We also define the mean-free path λ as the averaged moving distance that one traverses before encountering the next walker. Because the walker continues to repeatedly travel around and return home, the spatial existence probability of the focused walker tends to increase as the distance from home decreases. With this viewpoint in mind, we assume that the contact frequency for this walker and others depends only on the distance from home r ′ and that the walker meets the same walker at the same distance. Taking into consideration all of

✠

Fig. 6. Typical CCDFs for contact frequency values ¯ ( F x ) employing RW and HRW in numerical simulations where N = 10 3 , T = 10 [ ] 5 s , and α = 0 0 2 0 5 , . , . (dots).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-1dbd4d52-386f-4de9-aa50-8d65e8fb0aa6.jpg)

Fig. 7. Typical CCDFs for contact frequency values ¯ ( F x ) employing RWP and HRWP in numerical simulations where N = 10 3 , T = 10 [ ] 5 s , and α = 0 0 2 0 5 , . , . (dots).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-6d75d5c0-c32a-45bc-8473-4c327571810c.jpg)

the above definitions and assumptions, we envision a scenario in which the walker encounters a new walker whenever he walks away from the concentric rings of width λ whose centre is his home. This image of meetings with walkers is used to separate the space into many ring-shaped concentric zones in which the walker in question meets others, as shown in Fig. 8. We call this the concentric zone hypothesis .

In Fig. 9(a), we present numerical results for the CCDF of the walker's frequency of contact with others with respect to his distance from home and the location at which he encounters those other individuals, ¯ H . We observe that the function ¯ H generally obeys a power-law distribution for α &gt; 0 , especially for the lower range of r ,

$$\bar { H } ( r ^ { \prime } \geq r ) \sim r ^ { - \tilde { \beta } }, \text{ \quad \ \ } ( 4 )$$

where ˜ β is the power index. The cut-off of the power law at the tail arises from the effect of spatial boundedness. For

Fig. 8. Schematic illustration of the concentric zone hypothesis.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-f88d6596-af7b-427f-87f4-8aba68db6997.jpg)

α = 0 , however, ¯ H is more likely to behave like a uniform distribution than it is to behave like a power law. Therefore, the spatial existence probability ¯ H appears to be qualitatively different for HLW and LW.

In Fig. 9 (b), we showed the numerical results indicating how the power index ˜ β behaves given changes in α and β . We can see that a proportional relationship between ˜ β and β ,

$$\tilde { \beta } \simeq c \beta + d,$$

is approximately satisfied for small α and 0 ≤ β ≤ 1 . The proportionality coefficient c α ( ) in Eq. (5), which seems to have a particular value when α is fixed, tends to gradually decrease with increasing α . These values of c α ( ) for α = 0 1 . , 0 2 . , 0 3 . , 0 4 . , 0 5 . varies around one.

Applying the power-law distribution of ¯ H to the concentric zone hypothesis allows us to calculate the contact frequency of the walker in the j -th concentric ring zone, denoted as x j . For this purpose, we use h r ( ) ≡ -dH r ¯ ( ′ ≥ r /dr ) as follows:

$$x _ { j } & \ \stackrel {. } { \approx } \ \int _ { j \lambda } ^ { ( j + 1 ) \lambda } h ( r ) r d r \sim \int _ { j \lambda } ^ { ( j + 1 ) \lambda } r ^ { - ( 1 + \tilde { \beta } ) } r d r \\ & \ \stackrel {. } { \approx } \ \lambda ^ { 2 } j / ( j \lambda ) ^ { 1 + \tilde { \beta } } \ \in j ^ { - \tilde { \beta } }.$$

This equation directly indicates that the rank distribution of the contact frequencies also obeys a power-law distribution whose power index is ˜ β . When β remains within its small range 0 ≤ β &lt; (1 -d /c ) , the power index of the rank distribution ˜ β becomes less than one by Eq. (5). In this case, therefore, the tail of the rank distribution is generally so wide that the number of low-ranked walkers is divergent, which provides a simple explanation of why the majority of human encounters is Ichigo Ichi-e.

We also consider the relationship between the rank distribution and the CCDF for contact frequency. It is well-known that if a rank distribution obeys a power law, then its frequency also becomes a power law. Thus, for the rank distribution x j , we can obtain the scale-free human contact frequency. In this case, it is also known that an inverse relationship exists between k and ˜ β :

$$k = 1 / \tilde { \beta } \simeq 1 / ( c \beta + d ).$$

We checked whether this inverse relation is numerically supported in Fig. 10. We can see that Eq. (7) roughly explains

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-316aa6a3-58c2-4f78-a9c3-d645eb4f1da0.jpg)

✍

✌

Fig. 9. (a) A typical spatial existence probability distribution ¯ ( H r ′ ≥ r ) for HLWs where N = 10 3 , T = 10 [ ] 5 s , α = 0 0 1 0 2 0 3 0 4 , . , . , . , . , and β = 0 2 . (dots). The power index ˜ β is also shown using the least-square fits for the distribution (solid line). (b) The relationship between the parameters α = 0 1 0 2 0 3 0 4 . , . , . , . , 0 5 . and 0 ≤ β ≤ 1 and the estimated power index ˜ β (line with dots) and their least-square fits (line).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-b4240b27-ab67-4ea2-bb13-d0e851050b83.jpg)

the trend between k and ˜ β . Substituting controlled values of 0 ≤ β &lt; (1 -d /c ) into Eq. (7) yields values of k ( &gt; 1 ) that are consistent with the experimental presented in Tables I and II.

## VI. CONCLUSION

In summary, we investigated the general statistical properties of serendipitous human encounters in daily life using portable wireless communication devices. We experimentally determined that we can universally apply the following statistical principles to human contact frequencies among individuals:

- 1) The majority of human encounters occur once during one's experimental period and this feature seems to continue during one's lifetime (the property of Ichigo Ichi-e)
- 2) The remaining, more frequent encounters obey the power-law distribution in terms of contact frequency and its variance diverges (the scale-free property)

✏

Fig. 10. Relation between k and ˜ β for α = 0 1 0 2 0 3 0 4 0 5 . , . , . , . , . and 0 ≤ β ≤ 1 (dots) and the exact inverse relationship in Eq. (7) (solid line).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0427v1-figure-7056bb8d-9e44-416d-9138-c2e110656b98.jpg)

Because this long tail principle of human contact frequency is universal, it is difficult to predict how many times we will have additional opportunities to meet with people over long periods of time. This further validates the principle of Ichi-go Ichi-e, which teaches us to 'treasure every encounter.'

To facilitate a fundamental theoretical understanding of these principles, we introduced a novel stochastic model of human mobility traces called the 'homesick L´ evy walk.' We used numerical simulations to demonstrate that this model can successfully explain both of the principles. Furthermore, using simple mean-field theory, we determined that the origin of the principles arises from the following two opposing mechanisms that inherently underlie human mobility patterns:

- 1) Long-distance travelling ( 0 ≤ β &lt; (1 -d /c ) in HLW)
- 2) Homesickness ( α &gt; 0 in HLW)

Although we have proposed this model in [22], [23] for evaluation our proposed routing method, the origin of the above properties is first explained in this paper. Balancing the two mechanisms leads the statistical principles of human contact frequency to emerge. Note that according to violating the first mechanism, 'Homesick Random Walk (HRW)' whose walk length to the next destination is determined by a distribution with a finite variance does not have the scale-free property of contact frequency, which we have also checked numerically.

It should be noted that we have introduced home as a minimum social effect. Because homesick L´ evy walkers periodically return to their home, they tend to stay longer around their homes. Therefore, they meet with each other more frequently as the distance between their homes is closer, which naturally includes social relations between the walkers.

## VII. DISCUSSIONS

In this paper, we focused on contact frequency for humans . However, that of animals might also obey the same principles because the above two mechanisms are common to animals and humans: animals usually have nests that are similar to our homes, and they also travel to distant feeding sites.

For future works, it is also important to consider effects of non-uniformity of population density. In the simulations, we used the average population density of Japan, but the density of people highly varies by the size of city where they live. Effects of the density on contact frequency, inter-contact time, and contact duration is an interesting task to investigate.

Recently, Song et al. has proposed 'preferential return' to explain spatial visitation properties of human mobility patterns using their individual mobility model [18]. Our homesick L´ evy walk model seems to be similar to their model, but there are some differences: Since they consider the visitation frequency of locations, their model needs multiple locations where one can return preferentially by flight . Since we consider the contact frequency between humans, on the other hand, our model does not necessarily assume multiple locations, but only one hub location where one can return with a fixed probability by walk . By experiment, we empirically know that the serendipitous human contacts occur on the way to destination more frequently rather than duration of visit at destination. Therefore, theoretical results given by their model does not cover statistical properties of the majority of human contacts. To understand the relation between these models is left for future work.

We think our mobility model is useful for performance evaluation of routing protocols in Delay Tolerant Networks (DTN) [19] since some protocols selects routing paths with frequent encounters in utility-based routing protocols, such as PRoPHET [20], MAXPROP [21], and so on. We also have proposed our algorithm for routing in DTN and have shown some results regarding the comparison between LW and HLW [22], [23], which indicates that the arrival rate of transferred messages tends to be much lower as increasing the homesick probability α . It is also important to take into consideration the effect of Ichi-go Ichi-e since the large number of human encounters is rare. Therefore, the majority of human encounters usually doesn't contribute to the performance of the utility-based routing, but they only consume much memory in vain for memorizing the history of encounters with many nodes that will never be encountered again. After understanding the properties of the frequency of human contact well, the routing protocols for message transfer could be improved.

## ACKNOWLEDGMENT

This work is partially supported by Japan Society for the Promotion of Science through Grant-in-Aid for Scientific Research (C) (23500105) and Grant-in-Aid for Young Scientists (B) (25870958).

## REFERENCES

- [1] Song, C., et al. Limits of Predictability in Human Mobility, Science, vol. 327, no. 5968, pp.1018-1021 (2010).
- [2] Y.-A. de Montjoye, et al. , Unique in the Crowd: The privacy bounds of human mobility, Scientific Reports, vol. 3, no. 1376 (2013).
- [3] Roy, R. R. Handbook of Mobile Ad Hoc Networks for Mobility Models (Springer, 2011).
- [4] Santi, P. Mobility Models for Next Generation Wireless Networks: Ad Hoc, Vehicular and Mesh Networks (Wiley, 2012).
- [5] Lee, K. et al. SLAW: Self-Similar Least-Action Human Walk, IEEE/ACM Transactions on Networking, vol. 20, no.2, (2012).
- [6] Denko, M. K. Mobile Opportunistic Networks: Architectures, Protocols and Applications (Auerbach Publications, 2011).
- [7] Woungang, I., et al. Routing in Opportunistic Networks (Springer, 2013).
- [8] http://tech.pokutuna.com/android-wireless-device-logger/
- [9] ben-Avraham, D. &amp; Havlin, S. Diffusion and Reactions in Fractals and Disordered Systems (Cambridge University Press, 2000).
- [10] Barab´ asi, A.-L. Bursts: The Hidden Pattern Behind Everything We Do (Dutton Adult, 2010).
- [11] Brockmann, D. et al. The scaling laws of human travel. Nature 439 462-465 (2006).
- [12] Gonz´ alez, M. C. et al. Understanding individual human mobility patterns. Nature 453 , 779-782 (2008).
- [13] Rhee, I. et al. On the Levy-walk Nature of Human Mobility: Do Humans Walk like Monkey? The 27th IEEE International Conference on Computer Communications (IEEE INFOCOM 2008), 924-932 (2008).
- [14] Viswanathan, G. M. et al. Optimizing the success of random searches. Nature 401 , 911914 (1999).
- [15] Edwards, A. M. et al. Revisiting L´ evy flight search patterns of wandering albatrosses, bumblebees and deer. Nature 449 , 1044-1048 (2007).
- [16] David W. Sims et al. Scaling laws of marine predator search behaviour. Nature 451 , 1098-1102 (2008).
- [17] Viswanathan, G. M. et al. The Physics of Foraging: An Introduction to Random Searches and Biological Encounters (Cambridge University Press, 2011).
- [18] C. Song et al. , Modelling the scaling properties of human mobility, Nature Physics (Advanced Online Publications) 7, 713 (2010).
- [19] A. Vasilakos, Y. Zhang, and T. V. Spyropoulos, Delay Tolerant Networks: Protocols and Applications , Wireless Networks and Mobile Communications Series, CRC Press, 2012.
- [20] A. Lindgren, A. Doria, and O. Schel´ en, 'Probabilistic routing in intermittently connected networks,' ACM SIGMOBILE Mobile Computing and Communications Review, Vol. 7 Issue 3, pp.19-20(2003).
- [21] J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine, 'MaxProp: Routing for vehicle-based disruption-tolerant networks,' In Proc. IEEE INFOCOM, 398-408 (2006).
- [22] A. Fujihara, S. Ono, and H. Miwa 'Optimal Forwarding Criterion of Utility-based Routing under Sequential Encounters for Delay Tolerant Networks,' Third International Conference on Intelligent Networking and Collaborative Systems (INCoS) 2011, 279-286 (2011).
- [23] A. Fujihara and H. Miwa, 'Homesick L´ evy Walk and Optimal Forwarding Criterion of Utility-based Routing under Sequential Encounters,' Internet of things and inter-cooperative computational technologies for collective intelligence, Studies in Computational Intelligence, vol. 460, pp. 207-231 (2013).
Akihiro Fujihara Hiroyoshi Miwa
Homesick Lévy walk: A mobility model having Ichi-go Ichi-e and scale-free properties of human encounters
In recent years, mobility models have been reconsidered based on findings by
analyzing some big datasets collected by GPS sensors, cellphone call records,
and Geotagging. To understand the fundamental statistical properties of the
frequency of serendipitous human encounters, we conducted experiments to
collect long-term data on human contact using short-range wireless
communication devices which many people frequently carry in daily life. By
analyzing the data we showed that the majority of human encounters occur
once-in-an-experimental-period: they are Ichi-go Ichi-e. We also found that the
remaining more frequent encounters obey a power-law distribution: they are
scale-free. To theoretically find the origin of these properties, we introduced
as a minimal human mobility model, Homesick L\'evy walk, where the walker
stochastically selects moving long distances as well as L\'evy walk or
returning back home. Using numerical simulations and a simple mean-field
theory, we offer a theoretical explanation for the properties to validate the
mobility model. The proposed model is helpful for evaluating long-term
performance of routing protocols in delay tolerant networks and mobile
opportunistic networks better since some utility-based protocols select nodes
with frequent encounters for message transfer.