# Preferential attachment in face-to-face relations

S. Plaszczynski<EMAIL_ADDRESS>B. Grammaticos  M.
Badoual  Université Paris-Saclay, CNRS/IN2P3, IJCLab, 91405 Orsay, France
Université Paris-Cité, IJCLab, 91405 Orsay France

###### Abstract

##### Abstract

We propose a stochastic model to describe the dynamics of contact duration in
face to face interactions. It reproduces precisely the deviations from the
mean-time that were found to be statistically very similar in several
environments. The model is based on geometric graphs built from points of a
Levy walk. It has a single parameter, the Levy index, that is found to be
$\alpha\simeq 1.1$ on all the datasets. In this model, the duration of
contacts in face to face interactions, which corresponds to the length of
discussions for humans, is related to the size of the connected components
(clusters) of the Levy graph. We compute analytically the distribution of the
clusters size which is of stretched-exponential type and reveals the dynamics
of the process. A discussion starts about a topic that is first developed,
which, in the Levy framework is described by a geometric distribution. It is
then driven by a preferential attachment mechanism; the more a discussion
lasts, the more it is likely to continue since there are more points to come
back to. This leads to heavy tails in the contact duration. The combined
behavior is well captured by the formation of clusters in Levy graphs. We show
it has some similarities with the case of a growing network with a sub-linear
power-law kernel. More precisely, in this model discussions appear as an
aggregation process with a natural scale fixed by the mean interaction time
between the individuals.

## Introduction

Communication networks as face-to-face ones are described by time-varying
graphs which are difficult to characterize because of the intertwining of the
topological and temporal aspects [1, 2]. However, the sociological mechanisms
that drive people encounters may actually be different from the ones that are
involved when two individuals actually “interact”. Since in the following we
only consider cases where people are face-to-face for at least 20 s, this
means for humans that a discussion is engaged. It could follow some universal
rules that lie out of the social context as stipulated in the field of
Conversation Analysis [3]. This is suggested by a recent analysis [4] of the
sociopatterns data (see SMAppendix, S1 for their description). It was shown
there that while the mean-time we spend together with a given person varies
according to our preferences but also to the sociological context, the
deviations from it seem to present a universal distribution. Most often we
tend to allocate short times to our exchanges with a given individual (with
respect to the usual mean-time) but very long discussions may emerge. What is
remarkable is that the statistical distribution of this deviation, in
particular for large values, looks the same in very different environments as
between scientists at a conference or between farmers in a small Malawi
village. This could point to some general properties of human face-to-face
interactions, or more generally of primates since similar results were
observed in a baboon population [4].

We try to model here the invariant distribution observed on what was called
the “contact duration contrast” (or simply “contrast”) which is simply, for
each relation (pair of individuals), the duration of contact divided by its
mean-time. We have little indication on how to build such a model but we may
rely on a very common mechanism that was dubbed “preferential attachment” in
network science [5]. Introduced to explain the emergence of power-law degree
distributions in real-life networks [6, 7, 8], it has in fact been studied by
scientists under different forms since a century [9, 10, 11]. It is even known
in common language, as “Matthew effect” \dagger\dagger$\dagger$Because of the
sentence in the Bible “ For unto every one that hath shall be given, and he
shall have abundance […] ” (Matthew 25:29). It formalizes the idea of the
“rich get richer” effect. For instance

  * •

when a paper is abundantly cited, it is more likely to be known by others and
thus cited even more [11, 5]. In the same vein, the more someone gets social
rewards the more it is likely to be known by others and receive even more
[12].

  * •

in the so-called Yard-Sale model [13] a pair of agents bets a fraction of
wealth of the poorest of the two with equal probability to win. Running such a
system with several agents, the pairs being randomly selected, finally leads
to “oligarchy”, i.e. a single agent concentrates all the wealth [14]. This is
due to a rich-get-richer effect; when there is imbalance, it is less risky for
the rich to bet some small amounts than for the poor, which further
accentuates imbalance.

  * •

in colloidal solutions, the more an aggregate grows, the more it is likely to
be hit by particles and become even larger.

Discussions also hold a preferential-attachment mechanism. Everyone
experienced that when a conversation lasts for long, it is likely to last even
more. One can hardly escape it since there are more and more potential topics
to come back to.

We propose a model to describe the dynamics of the discussion evolution,
initially motivated by a coincidence on the shape between two distributions.
It is based on geometric graphs build from the points of a Levy walk [15] that
are first reviewed in sect. I. Then we tune our empirical model to investigate
at which level it can match the sociopattern data in sect. II. This single-
parameter model gives excellent results. Investigating the dynamics of
clusters formation we show analytically why in sect. III. Since the process we
propose resemble that of a growing network [16], we compare them in more
details in sect. IV. Finally in sect. V, we comment on the geometric nature of
the model and emphasize why, in the class of all random-walks, only Levy
flights can be suitable candidates to model discussions through a geometric
graph. Appendix A explains what the self-similarity of a Levy flight precisely
means, and why it gives rise to several scaling relations in Levy graphs. Some
auxiliary results are available in the Supplementary Material (SM).

##  I Levy flights, graphs and clusters

A Levy flight, as introduced by B. Mandelbrot [17, 18] is a random-walk
process but unlike the standard case where each step follows a Gaussian
distribution (or converges to it due to the Central Limit Theorem, CLT), the
length of the jumps follow a power-law distribution, namely a Pareto-Levy one
[19]. The probability for a step length to exceed some value $R$, i.e. the
complementary cumulative density function (CCDF) is

$\displaystyle P(r>R)=\begin{cases}1&\text{if}\leavevmode\nobreak\ r\leq
r_{0},\\\ (r_{0}/R)^{\alpha}&\text{else}\end{cases}$ (1)

where $r_{0}$ is a cutoff that ensures the proper probability density function
normalization, and $0\leq\alpha\leq 2$ is called the Levy index. In the
following we will work in units of $r_{0}$ so that, without loss of
generality, we set $r_{0}=1$. We emphasize that the step length is always
larger than $r_{0}=1$ as is more apparent on the the probability density
function

$\displaystyle f(r)=\dfrac{\alpha}{r^{\alpha+1}}\Theta(r-1),$ (2)

where $\Theta$ is the Heaviside step function.

This power-law form implies infinite variance and also in some cases
($\alpha\leq 1$) infinite expectation value. The random walk, i.e. the
cumulative sum of independent steps distributed this way, fail the CLT and
does not converge to a Gaussian distribution. Instead, following the work of
P. Levy [20, 21], it was shown that it has a basin of attraction to what is
known as $\alpha-$stable distributions (see e.g., [22]). This is called the
Generalized Central Limit Theorem [23, 24] (the Gaussian case is recovered for
$\alpha=2$).

A Levy flight can be simulated in a space of any dimension by drawing
isotropically a direction, and a radial part following eq. 1. We will mostly
focus our attention on dimension 2, since it is the dimension for which the
model best describes the data. In this case, the probability to return close
to a previous point of the walk, which we loosely call the “return-
probability” is most important.

The Levy flight trajectory has a fractal dimension $\alpha$ [25]; the mean
density of points within a sphere of radius $R$ localized on one of the point
of the flight, varies as $1/R^{2-\alpha}$ [17, 15]. The process is
statistically self-similar; loosely speaking the pattern of points “looks the
same” at any scale. A more precise description is given in Appendix A. We will
see that, due to this self-similarity, several power-law distributions
(scaling relations) emerge. An introduction to the (rich) theory of Levy
flights is given in [26].

A distinct feature of Levy flights is their clustering properties. Several
points of the walk end nearby before a long jump triggers the construction of
another cluster. Because of the absence of scale in eq. 1 a nested hierarchy
of self-similar clusters is created [27].

To study the clusters’ properties we introduce explicitly a scale $s$ and
build a geometric graph, i.e. join the points of the walk to form edges if
their distance is below a fixed value $s$. This leads to a family of graphs
$\mathscr{L}_{\alpha}(s)$, called “Levy Geometric Graphs” which were studied
in [15]. They consists in a set of connected-components that we call (Levy)
“clusters”. An example is show in Fig. 1. Although not (yet) justified, it was
noticed that the mean number of clusters for a Levy graph of size $N$ scales
as

$\displaystyle\langle N_{\text{c}}\rangle/N=A_{c}/s^{\alpha_{c}},$ (3)

where $A_{c}\to 1,\leavevmode\nobreak\ \alpha_{c}\to\alpha$ in a large
dimension space. Those parameters are obtained from simulations in low
dimensions and given in SMAppendix, S3.

Figure 1: Example of construction of Levy clusters. (a) Levy flight. The
points are obtained from a random Levy walk of index $\alpha=1.1$ and the line
shows their creation path. (b) Levy graph. The points form the vertices of a
graph with edges connecting pairs if their distance is inferior to the scale
$s$ (here $s=3$). (c) The connected components of the graph form Levy clusters
which are colored the same. In our model, their size represent the duration of
contact between two individuals and the scale is related to their interaction
mean-time.

##  II An empirical model of discussion

An intriguing fact is that the cluster size contrast for Levy graphs (Fig.8 of
[15]), i.e. $n_{i}/\bar{n}$ where $n_{i}$ denotes the size of the connected
components, has a distribution that looks similar to what is observed for the
duration of contacts in the sociopatterns data (Fig.4 of [4]). We thus try to
match a model based on Levy graphs to the description of the observed duration
contrast. To this purpose, on each sociopatterns dataset, we extract the set
of all relations $r$ and compute their total $w(r)$ and mean $\bar{t}(r)$
interaction time. Then, for each relation we generate a 2D Levy graph of size
$N=w(r)$ \dagger\dagger$\dagger$Since we use raw data, $w(r)$ is expressed in
units of the resolution step and has thus an integer value.. To match the
observed mean-time to the mean cluster size we use eq. 3

$\displaystyle\langle
N_{\text{c}}\rangle/N=1/\bar{n}=A_{c}/s^{\alpha_{c}}=1/\bar{t},$ (4)

which sets the scale to

$\displaystyle s(r)=\left[A_{c}\bar{t}(r)\right]^{1/\alpha_{c}},$ (5)

where the $A_{c}(\alpha)$ and $\alpha_{c}(\alpha)$ values are taken from
SMAppendix, S3. We then extract the connected-components of the graph and
measure their size ($n_{i}$) and compute the cluster size contrast
$\delta_{i}=n_{i}/\bar{n}$ distribution. Since the graph is random, we repeat
the procedure 10 times and superimpose the results. The only free parameter in
the model is the Levy index $\alpha$.

Figure 2: Comparison between the cluster size distribution contrast (CCDF) of
the Levy model defined in the text for 3 indices ($\alpha=0.5,1,1.5$) and the
contact duration contrast measured from the sociopatterns data recorded in a
Malawi village [28]. Each line of the same color represents a different
realization of the random graph. Figure 3: Comparison between the cluster size
distribution contrast of the Levy model with a $\alpha=1.1$ index and the
contact duration contrast measured from the sociopatterns data recorded in a
Malawi village [28].

We show how the distributions vary for some $\alpha$ values on Fig. 2. There
is little spread among the different realizations and a value of $\alpha$
around 1 is close to the data. We find that a value of $\alpha=1.1$ gives the
best agreement with the data as shown on Fig. 3. The agreement is excellent
and it is also the case on three other datasets using the very same
$\alpha=1.1$ value (see SMAppendix, S2) while the set of relations and their
characteristics are extremely different [4].

##  III Justification of the model

Although the agreement of the model with the data is impressive, it clearly
lacks justification. To this purpose we need to understand how clusters form
during the evolution of the Levy flight, i.e. the dynamic of clusters
formation in this peculiar form of random-walk. We proceed thus to computing
analytically the distribution of the clusters size for any Levy geometric
graph.

###  III.1 The dynamics of Levy clusters formation

We consider how clusters grow in a Levy graph when new points enter the
flight. Fig. 4 shows some typical cases for the clusters growth.

Figure 4: Example of two clusters obtained on a $\mathscr{L}_{1}(3)$ graph.
The numbers indicate the order of appearance of the points during the flight.
Points are colored according to the cluster they belong to. The edges show
pairs connected when their distance is below $s=3$.

  * •

The yellow cluster consists of three points (7,8,9), each being connected to
the previous one This is a case where the distances between the consecutive
steps all fall below the chosen scale (here $s=3$). For reasons that will
become clear later we call this the geometric configuration.

  * •

The light-blue cluster (0,1,2,3,4,5,6) shows a more evolved configuration.
Points are linked to their predecessors but for the (4-5) pair where the
distance exceeds the scale. Point (5) is however close enough to (0), and
later to (6), to be incorporated into the cluster. This effect is due to what
we call the return (or trapping) probability which increases when there are
more points. It is a “rich-get-richer” mechanism which will be investigated
later.

Although both aspects are intimately related, we consider them first
separately in order to understand their properties.

####  III.1.1 The geometric case

Let us imagine that we can switch off the angular part in the jumps keeping
only the radial distribution eq. 1. This is in fact possible, by performing a
Levy flight on a 1D line but always in the same direction. One can approach
also this regime by increasing the dimensionality of the space. Indeed in many
dimensions it becomes very unlikely that a new jump connects to a previous
point of the walk since it will most often go into other parts of the space.
Let us call a “success” a jump that exceeds the distance $s$. Without a return
probability, the only way to form a cluster is by linking the new point to the
previous one. To form a cluster of size $n$, one then needs $n-1$ consecutive
“failures”. The corresponding probability is the geometric distribution

$\displaystyle\mathscr{G}(n)=p_{0}(1-p_{0})^{n-1},$ (6)

where $p_{0}$ is the probability to escape the cluster, which, according to
eq. 1, is

$\displaystyle p_{0}=1/s^{\alpha},$ (7)

and $n$ starts at 1 (the minimal cluster size). The expectation value for the
size of a cluster is

$\displaystyle\mathbb{E}\left[n\right]=1/p_{0}=s^{\alpha},$ (8)

in agreement with eq. 3 for a large dimension space, since the mean number of
clusters in a graph of size $N$ is $\langle N_{\text{c}}\rangle=N/\langle
n\rangle$. We show in Fig. 5, using simulations, that when increasing the
dimension of the space for the Levy flight, the cluster size distribution
converges indeed to the geometric one.

Figure 5: Distribution of the clusters size for a $\mathscr{L}_{1}(5)$ graph
obtained by simulation ($N=10^{6}$ steps) increasing the space dimensionality
$d$ (points). The distributions converge to the geometric form (black line).

We now consider the walk in dimension 2 where the effect of the return-
probability cannot be neglected especially for large clusters (Fig. 5). To
gain intuition on its effect on cluster formation we would like to cancel the
geometric configuration. This may be performed in the following way.
Remembering that a single Pareto-Levy step always produces a point at a
distance beyond $r_{0}=1$ (eq. 2), if we construct a Levy graph at a scale
$s=1$ or below, two consecutive points can never get connected. Without a
return probability, this would lead only to a set of singlet clusters. However
the return-probability brings back some points from the walk close to previous
ones opening the possibility to create Levy clusters with more than a single
vertex. Fig. 6 shows the resulting distributions obtained in simulations with
a scale $s=1$ and varying the Levy index. They fall steeply and converge to a
power-law as $\alpha$ reaches 2, which will be confirmed analytically later.
The emergence of heavy tails that are close to power-law ones is typical of a
preferential-attachment mechanism that we shall now investigate.

Figure 6: Distribution of 2D Levy clusters size with a scale $s=1$ for
$\alpha=1,1.5$ and 2.

####  III.1.2 Preferential attachment

As presented in the introduction, discussions benefit from a preferential
attachment effect: when they last for long it is likely they will extend even
more. It becomes more and more difficult to escape a conversation while it
lasts. This feature is captured in our model by the Levy clusters. When the
size of a cluster increases, its trapping probability increases too; it gets
more and more difficult to escape the cluster, i.e. fall in a region of the
space far from the cluster points. We may get an order of magnitude of this
effect with the following argument. In 2D in average, $k$ points in a cluster
occupy an area $\pi R_{c}^{2}$, so that the mean cluster radius varies as
$R_{c}\propto\sqrt{k}$. The probability to escape the cluster with a single
step, i.e. perform a step beyond $R_{c}$ is then of the order of (see eq. 1)

$\displaystyle p(r>R_{c})\propto\dfrac{1}{k^{\alpha/2}}.$ (9)

While $k$ increases the success probability (to escape the cluster) decreases.
A cluster of size $n$ occurs when there are $n$ consecutive failures. We thus
generalize the geometric form eq. 6 to

$\displaystyle p(n)\propto{\prod_{k=1}^{n}(1-p_{0}(k))},$ (10)

where

$\displaystyle p_{0}(k)=\dfrac{A}{k^{\gamma}},$ (11)

and $\gamma$ should be close $\alpha/2$. The normalization is given by
$\sum_{n}p(n)=1$ and the geometric configuration is recovered by canceling the
preferential attachment term with $\gamma\to 0$ and $A\to p_{0}=1/s^{\alpha}$.

We confront this formula to the measured cluster sizes obtained in
simulations, performing a least-squares minimization on $A$ and $\gamma$, for
several values of $\alpha$ and $s$ varied in the range $0.8\leq\alpha\leq 1.4$
and $3\leq s\leq 10$. We obtain an excellent agreement in each case as shown
on some examples in Fig. 7.

Figure 7:  Clusters size distribution obtained from Levy graphs simulations
for some $\alpha$ and $s$ values (points). The curves show the corresponding
eq. 10 model, adjusting the $A$ and $\gamma$ parameters with least-squares
minimization.

We now consider the values of $\gamma$ and $A$ extracted from the fits. As
shown in Fig. 8 the exponent $\gamma$ depends essentially on $\alpha$ and at
large scales (corresponding to large $R_{c}$ in eq. 9) converges indeed to
$\alpha/2$.

Figure 8: Ratio between the $\gamma$ parameter of eq. 10 and $\alpha$
determined from $\mathscr{L}_{\alpha}(s)$ simulations varying $\alpha$ for
several scales $s$. The dashed line at 0.5 represents the eq. 9 expectation.
Figure 9: Value of the amplitude term $A$ in eq. 10 determined from
simulations as a function of the scale $s$ for several $\alpha$ values.

On the contrary, the amplitude term $A$ mostly depends on the scale as shown
in Fig. 9. Inspired by the fact that for singlet clusters ($n=1$) the
geometric distribution has an amplitude term of power-law form, we
parameterize the general case as

$\displaystyle A(s)=c/s^{\beta},$ (12)

and show in Fig. 10 the fitted values of the parameters $c$ and $\beta$. They
are mildly dependent on $\alpha$ and a linear adjustment gives

$\displaystyle c$ $\displaystyle=1.19+0.31\alpha$ (13) $\displaystyle\beta$
$\displaystyle=0.57+0.14\alpha$ (14)

For the discussion model $\alpha=1.1$, $c=1.5,\beta=0.7$.

Figure 10: Determination of the values of the $s$ and $\beta$ parameters in
the $A(s)=a/s^{\beta}$ parametrization of eq. 10 measured from simulations.
The lines show the best linear fits.

We thus have the whole description of the clusters size probability function

$\displaystyle
p(n;\alpha,s)\propto{\prod_{k=1}^{n}\left(1-\dfrac{c}{s^{\beta}k^{\gamma}}\right)},$
(15)

which may be further simplified. Since

$\displaystyle p(n)/p(n-1)=1-A/n^{\gamma},$ (16)

the logarithmic slope goes asymptotically as

$\displaystyle D=\dfrac{\ln{p(n)}-\ln{p(n-1)}}{\ln{n}-\ln{(n-1)}}\sim-
An^{1-\gamma},$ (17)

with $\gamma\simeq\alpha/2$. For $\alpha=2$ we obtain a pure power-law form as
was observed in Fig. 6. Considering the continuum case,
$D=\tfrac{n}{p}\tfrac{dp}{dn}$, we find that, for $\alpha<2$, the
distributions follows asymptotically that of a stretched exponential

$\displaystyle
p(n)\propto\exp{\left(-\tfrac{A}{1-\gamma}n^{1-\gamma}\right)}.$ (18)

Numerically it appears that this approximation is in fact good on the whole
range of cluster sizes as shown in Fig. 11.

The distribution for our model of discussion ($\alpha=1.1$) is

$\displaystyle p(n;\alpha=1.1,s\gg
1)\propto\exp{\left(-\dfrac{3.3}{s^{0.7}}n^{0.45}\right)}.$ (19)

Figure 11: Distribution of the clusters size (points) compared to the
stretched exponential model eq. 18 derived in the text (lines).

The generalization to a space of any dimension can be easily performed.
Adapting the argument leading to eq. 9 to a ball in a $d$ dimensional space

$\displaystyle\gamma=\alpha/d.$ (20)

When changing the dimension, the parameters $c$ and $\beta$ of the amplitude
term $A=c/s^{\beta}$ evolve but the asymptotic expression eq. 18 still holds
as shown in the SMAppendix, S4. When $d$ increases $\gamma\to 0$ and $c\to
1,\beta\to\alpha$ and the cluster size distribution converges to
$\exp(-n/s^{\alpha})$ which is the continuous extension of the geometric
function as was observed in Fig. 5.

###  III.2 Scaling relations

We may now compute the mean cluster size using the asymptotic expression. With
the shorthand notations $\mu=1-\gamma,\leavevmode\nobreak\
\lambda=A/\mu=c/(\mu s^{\beta})$

$\displaystyle\bar{n}=\dfrac{u}{v}=\dfrac{\int_{1}^{\infty}ne^{-\lambda
n^{\mu}}dn}{\int_{1}^{\infty}e^{-\lambda n^{\mu}}dn}.$ (21)

With the change of variable $t=\lambda n^{\mu}$ the denominator becomes

$\displaystyle v=\dfrac{\lambda^{-1/\mu}}{\mu}\Gamma(1/\mu,\lambda),$ (22)

where the incomplete $\Gamma$ function is defined by

$\displaystyle\Gamma(a,z)=\int_{z}^{\infty}t^{a-1}e^{-t}dt.$ (23)

Integrating by parts and performing a similar computation on the numerator
yields

$\displaystyle u=\dfrac{\lambda^{-2/\mu}}{\mu}\Gamma(2/\mu,\lambda^{2}),$ (24)

and the mean number of clusters finally reads

$\displaystyle\bar{n}=\dfrac{\lambda^{-1/\mu}\Gamma(2/\mu,\lambda^{2})}{\Gamma(1/\mu,\lambda)}.$
(25)

When the scale increases $\lambda=c/(\mu s^{\beta})\to 0$ and asymptotically
the mean cluster size scales with $s$ as

$\displaystyle\bar{n}=\dfrac{\Gamma(2/\mu)}{\Gamma(1/\mu)}\left(\dfrac{\mu}{c}\right)^{1/\mu}s^{\beta/\mu},$
(26)

This regime is however only reached for very large scales ($s\gtrsim 10$).
Although the $\Gamma(2/\mu,\lambda^{2})$ function in the numerator of eq. 25)
converges rapidly to $\Gamma(2/\mu)$, this is not the case for
$\Gamma(1/\mu,\lambda)$ in the denominator with $\beta\simeq 0.7$. Numerically
the variation of this term with $s$ in a limited scale range is smooth and
leads essentially to a constant correction term in eq. 26. This is shown in
Fig. 12 where we compare the results from simulations to eqs. 25 and 26. The
agreement is good given the uncertainties on the fitted $\gamma,c$ and $\beta$
parameters.

Figure 12: Mean clusters size of $\mathscr{L}_{\alpha}(s)$ graph’s measured on
the simulation (points) varying the scale for a few $\alpha$ values, compared
to the exact analytical model eq. 25 (full lines) and its approximation eq. 26
(dashed lines).

Because of the long jumps in the Levy walk, the formation of a cluster at a
given scale is essentially a local process. The walker almost never “comes
back” to a previous cluster after a long jump. Clusters are thus mostly
uncorrelated and Levy graph’s may be viewed as a “factory” of clusters. The
sum of sizes of the $N_{\text{c}}$ clusters equals the graph’s size

$\displaystyle\sum_{i=1}^{N_{\text{c}}}n_{i}=N.$ (27)

In the mean, each (independent) cluster contributes to $\bar{n}$ so that
$\langle N_{\text{c}}\rangle\bar{n}\simeq N$. This explains the origin of the
second scaling law on the fractional number of clusters (eq. 3)

$\displaystyle\langle N_{\text{c}}\rangle/N\simeq 1/\bar{n}\propto
1/s^{\beta/\mu}.$ (28)

###  III.3 The cluster size contrast distribution

We now have all that is needed to compute analytically the distribution of the
cluster size contrast variable $\delta=n/\bar{n}$, as observed in Figs. 2 and
3. Performing the change of variable $n\to n/\bar{n}$ using eqs. 18 and 26 and
normalizing the result, we obtain

$\displaystyle p(\delta)$
$\displaystyle=\dfrac{\mu\Gamma(2/\mu)}{\Gamma^{2}(1/\mu)}e^{-\left[\tfrac{\Gamma(2/\mu)}{\Gamma(1/\mu)}\delta\right]^{\mu}}\mathrm{with}\leavevmode\nobreak\
\mu$ $\displaystyle=1-\dfrac{\alpha}{2}$ (29)

Integrating the formula, we obtain the CCDF

$\displaystyle p(\delta>x)$ $\displaystyle=\int_{x}^{\infty}p(\delta)d\delta$
$\displaystyle=\dfrac{\Gamma[1/\mu,\left(x\Gamma(2/\mu)/\Gamma(1/\mu)\right)^{\mu}]}{\Gamma(1/\mu)}$
(30)

where the incomplete $\Gamma$ function is given by eq. 23.

For the discussion model, $\alpha=1.1$, we have

$\displaystyle p(\delta)$ $\displaystyle=3.9\leavevmode\nobreak\
e^{-2.8\delta^{0.45}},$ (31) $\displaystyle p(\delta>x)$
$\displaystyle=0.9\leavevmode\nobreak\ \Gamma(2.2,2.8x^{0.45}).$ (32)

We show in Fig. 13 the agreement of this formula with simulations. We also
added the contrast distribution of the Geometric contribution which reads [15]

$\displaystyle p(\delta>x)$ $\displaystyle=(1-p_{0})^{x/p_{0}}.$ (33)

It shows that short discussions are rather driven by the geometric term while
the tail arises from the preferential-attachment mechanism.

Figure 13: Distribution of the cluster size contrast for the discussion model
based on a Levy graph of index 1.1. The full black line represent the CCDF
measured from simulations and the dashed one the analytical formula derived in
the text (eq. 31). The red curve corresponds to the geometric contribution.

##  IV Discussions as an aggregation process

Our model somewhat resembles that of a growing network with a sub-linear
(power-law) kernel [16] In this model, nodes are added sequentially and
attached to previous ones with a probability related to their connectivity
$p(k)\propto k^{\gamma}$. Asymptotically, the average number of sites with $k$
links grows up linearly $N_{k}(t)=tn_{k}$ and [16]

$\displaystyle n_{k}$
$\displaystyle=\dfrac{\mu}{k^{\gamma}}\prod_{j=1}^{k}\left(1+\dfrac{\mu}{j^{\gamma}}\right)^{-1}.$
(34)

There are some similarities with our model (eq. 10) since for large $j$ values
$(1+\mu/j^{\gamma})^{-1}\simeq 1-\mu/j^{\gamma}$. There are however also a
number of important differences.

  * •

By construction, the network has a single connected-component and $k$ denotes
the vertices degree.

  * •

In growing networks, there is a single degree of freedom, the amplitude term
$\mu$ being related to $\gamma$ and $1<\mu(\gamma)<2$ which is not what we
measure for our amplitude term (Fig. 9).

  * •

The fact that there is a single cluster gives rise to the $\mu/k^{\gamma}$
pre-factor which does not appear in eq. 10.

The analogy with a growing network is thus limited although both approaches
lead to stretched exponential distributions. The discussion model should be
rather considered as an aggregation process \dagger\dagger$\dagger$The
difference between both processes was already outlined in [16]. Two points get
connected if their relative distance is below the scale $s$. This is
equivalent to considering some disks of diameter $s$ centered on each point
that get connected if they overlap (see Fig. 14). Clusters/discussions between
two individuals thus appear as aggregates of such disks with a natural radius
determined by those persons mean-interaction time (eq. 5). As the aggregate
(discussion) grows, it gets more likely for the next jumps of the disk to
“stick” to it (conversation continues) which illustrates again the
preferential attachment mechanism.

Figure 14: The formation of Levy clusters seen as an aggregation process. The
Figure is the same as Fig. 4 when drawing disks of diameter $s$ around each
vertex. Each discussion corresponds to a colored aggregate.

##  V Discussion(s)

We have computed analytically the cluster size distribution for any Levy
geometric graph and found it to be of stretched-exponential type. But more
importantly, we unraveled the mechanism by which clusters form and its analogy
with the way discussions develop.

The initial phase is described by a geometric distribution, which for a large
scale is the exponential one. For a fixed mean-value, it is the maximum
entropy distribution [29, 30]. It means that, beside its mean-time, there is
no prior information on the duration the conversation will take.

While more points are added to the cluster (discussion) it is more likely that
the next ones will be linked (related) since geometrically the trapping
probability increases. This is a preferential-attachment mechanism and
reproduces the idea that as a discussion lasts it is more likely to last even
more.

In this model, discussions appears as an aggregation process with a natural
size fixed by the (usual) mean-time of the relation. Considering a discussion
as a form of aggregation sounds reasonable. Our main finding is that
experimental data are very well reproduced when the points follow a 2D Levy-
flight of index $\alpha\simeq 1.1$.

The duration of each discussion, characterized in the model by a number of
points, is a discrete quantity expressed in units of the resolution step
($T=20s$ for the sociopatterns data). Obviously we want a model that is
independent from that resolution. With a better instrument (lower $T$) the
duration and mean-time values would increase. In the Levy model this means
changing the scale of the Levy graph (see eq. 5) along with its number of
points (size). Among the class of random-walks only a Levy flight is
resolution-independent. Indeed, when increasing the scale of any geometric
graph based on a standard (finite-variance) random-walk, we end-up with a
single cluster, the giant component. When increasing the resolution, such a
model would lead to a single conversation between the two individuals. On the
contrary, Levy-walk based graphs escape percolation [15]. Increasing the
scale, the size of the graph changes and there are still clusters. The
important point is that the cluster size/duration contrast
$\delta=n/\bar{n}=t/\bar{t}$ is independent from the scale as was derived in
eq. 29.

A (measured) value of $\alpha\simeq 1.1$ is nothing special in the class of
Levy processes, although there are some mathematical differences when crossing
the value $\alpha=1$ [31]. We note that several human activities exhibit a
power-law dependency with exponents around 1 (see e.g., [32, 33]) but keep in
mind that our process is more elaborate than a mere power-law distribution.
This could be a consequence of the “least effort principle”, as proposed by G.
Zipf [34] to explain several scaling exponents around 1 related to human
behavior (such as the word frequency), but a convincing explanation remains to
be found.

The fact that the random walk is performed in a space of dimension 2 is only
dictated by the data. A walk in a higher dimensional space fits the data less
well (SMAppendix, S5).

A “point” in our model denotes a time-unit. It could be related to a notion of
information or more generally to a “topic” (or concept). In the geometric
phase, which starts the discussion, each individual would discuss the initial
topic, each one answering to the previous “point”. The return-probability
would mean a break in this flow to a “point” previously raised. The
preferential-attachment mechanism would mean that while more topics have been
addressed it is more likely to get back to one of them. This is what is
observed on internet discussion feeds [35]. A person (“A”) posts some question
and gets an answer from “B”, and there might be an exchange between the two
leading to a “A-B-A…” sequence. This is what we identify as the geometric
phase. While the discussion goes on, third party users (“C”, then “D” etc.)
may enter the game, by commenting some part of the discussion which leads to
branches in the feed. The complexity of the discussion increases, sometimes to
a point where the whole exchange gets out of control in solving the initial
question. This evolution looks somewhat similar to what we observe in face-to-
face discussions but there are some important differences too (there are for
instance several participants in the feed). Testing whether such a hypothesis
for the meaning of the word “point” makes sense requires the tools of
Conversation Analysis [3].

## Conclusion

We have proposed a stochastic model to describe the duration of discussions
between two individuals. It reproduces precisely the distributions of the
contrast duration of contacts (i.e. the duration divided by the mean value for
each relation) on several datasets of face-to-face interaction recordings,
with a single parameter, the Levy index, that was found to be $\alpha\simeq
1.1$.

The model is based on some simple considerations about conversations. A
discussion always starts about a topic that is first explored. While it lasts,
it becomes more likely to last even more since there are more points to come
back to. Such a behavior can be reproduced by considering the size of the
clusters (connected components) in geometric graphs built from the points of a
Levy flight, named Levy Geometric Graphs [15]. We derive analytically the
cluster size distribution which is of stretched-exponential type. By dividing
it by the mean-value to obtain the dimensionless “duration contrast” variable,
we show that it becomes independent of the resolution. This is a necessary
requirement for the model which cannot be met by any other type of random-
walk. The analysis of the clusters dynamics reveals that they initially form
by linking each point to the previous one (geometric phase). Then as more
points are added more complex structure emerge due to the increasing return-
probability to some previous points (preferential attachment).

We also show that while the model shares some similarities with the case of a
growing network with a sub-linear kernel, it actually belongs to the class of
aggregation processes. The model may be viewed as a “disk” with a diameter
related to the mean-interaction time, that makes jumps following a Levy flight
of index 1.1 (see Fig. 14). The size of each set of overlapping disks
represents the duration of a discussion.

Finally we may question the very notion of discussion and language. We have
disregarded the fact that baboon’s interaction shows dynamics similar to human
one [4] and are thus also characterized in our model by a Levy index of
$\alpha=1.1$ (SMAppendix, S2). Although our communication through an evolved
verbal language is (probably) more complex than the baboons’ one, this calls
into question the very notion of “discussion” and the role of language on the
development of the human species [36].

###### Acknowledgements.

We thank Alexandre Delanoë for enlightening discussions on conversation
analysis and the analogy with internet discussion feeds. All graph-related
computations were performed with the graph-tool package [37].

##  Appendix A Levy flights self-similarity

To understand the origin of the scaling relations, we come back to the
individual points of the Levy walk, that we label with time and consider as
complex-valued, $X(t)$. Although the variance is formally diverging, one may
get a similar quantity by rescaling the lower-order fractional moments [31]

$\displaystyle\langle\lVert X(t)\rVert^{q}\rangle$ $\displaystyle\propto
t^{q/\alpha},$ $\displaystyle\langle\lVert X(t)\rVert^{q}\rangle^{2/q}$
$\displaystyle\propto t^{2/\alpha},$ (35)

where $0<q<2$ for convergence. This pseudo-mean squared displacement reveals
the super-diffusive nature of the walk, with a Hurst exponent (see e.g., [38])

$\displaystyle H=1/\alpha.$ (36)

This result may also be obtained on finite size samples [39] or using a
sliding window during the walk [40] or more rigorously with a Renormalization
Group approach [41]. Self-similarity corresponds to the fact that $X(t)$ and
$X(rt)/r^{H}$ are statistically indistinguishable for any $r$ value, i.e. that
the samples follow exactly the same underlying distribution (we illustrate it
with simulations in SMAppendix, S6). We note note it $X(t)\equiv X(rt)/r^{H}$.
Taking $r=1/s^{\alpha}$ and using eq. 36, we find that

$\displaystyle X(t)/s\equiv X(t/s^{\alpha}),$ (37)

This relation shows that rescaling the random function random $Y(t)=X(t)/s$ is
equivalent to sub-sampling the original process by a factor $1/s^{\alpha}$.
This is in line with the definition of the effective diffusion coefficient for
a Weierstrass random walk [27], the analog of a Levy flight but on a square
lattice of mesh size $a$, given by (see e.g., [22]) $D_{eff}=\lim_{a,\Delta
t\to 0}a^{\alpha}/\Delta t$.

A Levy graph of scale $s$ is constructed by linking points satisfying $\lVert
X(t_{i})-X(t_{j})\rVert<s$ or using the rescaled variable $\lVert
Y(t_{i})-Y(t_{j})\rVert<1$. Changing the scale is equivalent to varying the
graph’s size by $N/s^{\alpha}$ but otherwise keeping topologically equivalent
configurations. Then all statistics related to the graph’s size, vary with
$s^{\alpha}$. For instance, the faction of edges, average degree or mean
cluster size all scale with $s^{\alpha}$. The number of clusters, being the
inverse of the mean cluster size, eq. 28, scales inversely.

So why is the exponent we computed for the mean cluster size (eq. 26) not
exactly $\alpha$ but a more complicated function of it? The reason lies in
what we call the “Levy flight”. We have focused on the original definition
given by Mandelbrot [17], not on the one used to derive appendix A which is
based on steps following exactly a $\alpha$-stable distributions (as a Cauchy
one for $\alpha=1$). The Pareto-Levy distribution used throughout the text
(eq. 2) is not exactly a stable one, because of the gap below $r_{0}=1$.
However, because of the Generalized CLT [24], its cumulative sum (i.e. the
random-walk) converges rapidly to it. While for most observables it has very
little impact, it slightly affects the clusters size (which are often made up
from the very first points of the walk) which makes the calculation of their
distribution more elaborate.

## References

  * Holme and Saramäki [2012] Petter Holme and Jari Saramäki.  Temporal Networks.  _Physics Reports_ , 519(3):97–125, October 2012\.  ISSN 03701573.  doi: 10.1016/j.physrep.2012.03.001.  URL http://arxiv.org/abs/1108.1780.  arXiv: 1108.1780.
  * Holme [2015] Petter Holme.  Modern temporal network theory: a colloquium.  _Eur. Phys. J. B_ , 88(9):234, September 2015\.  ISSN 1434-6028, 1434-6036.  doi: 10.1140/epjb/e2015-60657-4.  URL http://link.springer.com/10.1140/epjb/e2015-60657-4.
  * Button et al. [2022] Graham Button, Michael Lynch, and Wes Sharrock.  _Ethnomethodology, Conversation Analysis and Constructive Analysis: On Formal Structures of Practical Action_.  Routledge, London, 1 edition, September 2022.  ISBN 978-1-00-322079-4.  doi: 10.4324/9781003220794.
  * Plaszczynski et al. [2024] Stéphane Plaszczynski, Gilberto Nakamura, Basile Grammaticos, and Mathilde Badoual.  On the duration of face-to-face contacts.  _EPJ Data Science_ , 13(1), January 2024.  ISSN 2193-1127.  doi: 10.1140/epjds/s13688-023-00444-z.  URL http://dx.doi.org/10.1140/epjds/s13688-023-00444-z.
  * Albert and Barabási [1999] Réka Albert and Albert-László Barabási.  Emergence of scaling in random networks.  _Science_ , 286(5439):509–512, October 1999\.  ISSN 1095-9203.  doi: 10.1126/science.286.5439.509.  URL http://dx.doi.org/10.1126/science.286.5439.509.
  * Albert et al. [1999] Réka Albert, Albert-László Barabási, and Hawoong Jeong.  Mean-field theory for scale-free random networks.  _Physica A: Statistical Mechanics and its Applications_ , 272(1–2):173–187, October 1999.  ISSN 0378-4371.  doi: 10.1016/s0378-4371(99)00291-5.  URL http://dx.doi.org/10.1016/S0378-4371(99)00291-5.
  * Krapivsky et al. [2000] P L Krapivsky, S Redner, and F Leyvraz.  Connectivity of Growing Random Networks.  _Physical Review Letters_ , 85(21), 2000.
  * Dorogovtsev et al. [2000] S N Dorogovtsev, J F F Mendes, and A N Samukhin.  Structure of Growing Networks with Preferential Linking.  _Physical Review Letters_ , 85(21), 2000.
  * E. and Yule [1925] F. Y. E. and G. Udny Yule.  A Mathematical Theory of Evolution Based on the Conclusions of Dr. J. C. Willis, F.R.S.  _Journal of the Royal Statistical Society_ , 88(3):433, May 1925.  ISSN 09528385.  doi: 10.2307/2341419.
  * Simon [1955] Herbert A. Simon.  On a class of skew distribution functions.  _Biometrika_ , 42(3-4):425–440, 1955.  ISSN 0006-3444, 1464-3510.  doi: 10.1093/biomet/42.3-4.425.
  * Price [1976] Derek De Solla Price.  A general theory of bibliometric and other cumulative advantage processes.  _Journal of the American Society for Information Science_ , 27(5):292–306, September 1976.  ISSN 1097-4571.  doi: 10.1002/asi.4630270505.  URL http://dx.doi.org/10.1002/asi.4630270505.
  * Merton [1968] Robert K. Merton.  The matthew effect in science: The reward and communication systems of science are considered.  _Science_ , 159(3810):56–63, January 1968.  ISSN 1095-9203.  doi: 10.1126/science.159.3810.56.  URL http://dx.doi.org/10.1126/science.159.3810.56.
  * Hayes [2002] Brian T. Hayes.  Follow the money.  _American Scientist_ , 2002.  URL https://api.semanticscholar.org/CorpusID:123614498.
  * Boghosian et al. [2015] Bruce M. Boghosian, Merek Johnson, and Jeremy Marcq.  An h theorem for boltzmann’s equation for the yard-sale model of asset exchange.  _Journal of Statistical Physics_ , 161:1339 – 1350, 2015\.  URL https://api.semanticscholar.org/CorpusID:254697740.
  * Plaszczynski et al. [2022] S. Plaszczynski, G. Nakamura, C. Deroulers, B. Grammaticos, and M. Badoual.  Levy geometric graphs.  _Phys. Rev. E_ , 105:054151, May 2022.  doi: 10.1103/PhysRevE.105.054151.  URL https://link.aps.org/doi/10.1103/PhysRevE.105.054151.
  * Krapivsky and Redner [2001] P. L. Krapivsky and S. Redner.  Organization of growing random networks.  _Physical Review E_ , 63(6):066123, May 2001.  ISSN 1063-651X, 1095-3787.  doi: 10.1103/PhysRevE.63.066123.
  * Mandelbrot [1975] Benoit Mandelbrot.  ”sur un modèle décomposable d’univers hiérarchisé: déduction des corrélations galactiques sur la sphère céleste.”.  _Comptes Rendus (Paris)_ , 280A:1551–1554, 1975.  URL https://users.math.yale.edu/mandelbrot/web_pdfs/comptes_rendus_79.pdf.
  * Mandelbrot [1983] Benoit Mandelbrot.  _The Fractal Geometry of Nature_.  Freeman, San Francisco, 1983.
  * Mandelbrot [1960] Benoit Mandelbrot.  The Pareto-Levy Law and the Distribution of Income.  _International Economic Review_ , 1(2):79, May 1960.  ISSN 00206598.  doi: 10.2307/2525289.
  * Lévy [1925] Paul Lévy.  _Calcul des probabilités_.  Gauthier-Villars, Paris, 1925.  ISBN 978-2-87647-231-0.
  * Lévy [1954] Paul Lévy.  _Théorie de l’addition des variables aléatoires_.  Gauthier-Villars, Paris, 1954.  ISBN 978-2-87647-207-5.
  * Paul and Baschnagel [2013] Wolfgang Paul and Jörg Baschnagel.  _Stochastic Processes_.  Springer International Publishing, Heidelberg, 2013.  ISBN 978-3-319-00326-9 978-3-319-00327-6.  doi: 10.1007/978-3-319-00327-6.
  * Khintchine [1938] A. Ya. Khintchine.  _Limit Distributions for the Sum of Independent Random Variables_.  O.N.T.I, Moscow (in russian), 1938.
  * Gnedenko and Kolmogorov [1954] B. V. Gnedenko and A. N. Kolmogorov.  _Limit Distributions for Sums of Independent Random Variables_.  Addison-Wesley, Reading, Mass., 1954.  ISBN 978-0-201-02420-3.
  * Seshadri and West [1982] V. Seshadri and Bruce J. West.  Fractal dimensionality of Lévy processes.  _Proceedings of the National Academy of Sciences_ , 79(14):4501–4505, July 1982.  ISSN 0027-8424, 1091-6490.  doi: 10.1073/pnas.79.14.4501.
  * Chechkin et al. [2008] Alexei V. Chechkin, Ralf Metzler, Joseph Klafter, and Vsevolod Yu. Gonchar.  Introduction to the Theory of Lévy Flights.  In Rainer Klages, Gnter Radons, and Igor M. Sokolov, editors, _Anomalous Transport_ , pages 129–162. Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim, Germany, July 2008.  ISBN 978-3-527-62297-9 978-3-527-40722-4.  doi: 10.1002/9783527622979.ch5.
  * Hughes et al. [1981] Barry D. Hughes, Michael F. Shlesinger, and Elliott W. Montroll.  Random walks with self-similar clusters.  _Proceedings of the National Academy of Sciences_ , 78(6):3287–3291, June 1981.  ISSN 0027-8424, 1091-6490.  doi: 10.1073/pnas.78.6.3287.
  * Ozella et al. [2021] Laura Ozella, Daniela Paolotti, Guilherme Lichand, Jorge P. Rodríguez, Simon Haenni, John Phuka, Onicio B. Leal-Neto, and Ciro Cattuto.  Using wearable proximity sensors to characterize social contact patterns in a village of rural Malawi.  _EPJ Data Science_ , 10(1):46, December 2021.  ISSN 2193-1127.  doi: 10.1140/epjds/s13688-021-00302-w.
  * Jaynes [1957] E. T. Jaynes.  Information Theory and Statistical Mechanics.  _Physical Review_ , 106(4):620–630, May 1957\.  ISSN 0031-899X.  doi: 10.1103/PhysRev.106.620.
  * Montroll and Shlesinger [1983] Elliott W. Montroll and Michael F. Shlesinger.  Maximum entropy formalism, fractals, scaling phenomena, and 1/f noise: A tale of tails.  _Journal of Statistical Physics_ , 32(2):209–230, August 1983.  ISSN 0022-4715, 1572-9613.  doi: 10.1007/BF01012708.
  * Metzler and Klafter [2000] Ralf Metzler and Joseph Klafter.  The random walk’s guide to anomalous diffusion: A fractional dynamics approach.  _Physics Reports_ , 339(1):1–77, December 2000\.  ISSN 03701573.  doi: 10.1016/S0370-1573(00)00070-3.
  * Song et al. [2010] Chaoming Song, Tal Koren, Pu Wang, and Albert-László Barabási.  Modelling the scaling properties of human mobility.  _Nature Physics_ , 6(10):818–823, 2010.  ISSN 1745-2473, 1745-2481.  doi: 10.1038/nphys1760.
  * Rybski et al. [2009] Diego Rybski, Sergey V. Buldyrev, Shlomo Havlin, Fredrik Liljeros, and Hernán A. Makse.  Scaling laws of human interaction activity.  _Proceedings of the National Academy of Sciences_ , 106(31):12640–12645, August 2009.  ISSN 0027-8424, 1091-6490.  doi: 10.1073/pnas.0902667106.
  * Zipf [1949] George Kingsley Zipf.  _Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology_.  Addison-Wesly Press, Inc., Cambridge 42. Massachusetts, 1949.
  * Delanoë and Conein [2015] Alexandre Delanoë and Bernard Conein.  Le contrôle de la forme des réseaux par leurs membres : le fil de discussion comme réseau d’interaction.  _SociologieS_ , May 2015.  doi: 10.4000/sociologies.5046.  URL https://doi.org/10.4000/sociologies.5046.
  * Heesen and Fröhlich [2022] Raphaela Heesen and Marlen Fröhlich.  Revisiting the human ‘interaction engine’: Comparative approaches to social action coordination.  _Philosophical Transactions of the Royal Society B: Biological Sciences_ , 377(1859):20210092, September 2022.  ISSN 0962-8436, 1471-2970.  doi: 10.1098/rstb.2021.0092.
  * Peixoto [2014] Tiago P. Peixoto.  The graph-tool python library.  _figshare_ , 2014.  doi: 10.6084/m9.figshare.1164194.  URL http://figshare.com/articles/graph_tool/1164194.
  * Peitgen et al. [2004] Heinz-Otto Peitgen, Hartmut Jürgens, and Dietmar Saupe.  _Chaos and Fractals_.  Springer New York, 2004.  ISBN 9780387218236.  doi: 10.1007/b97624.  URL http://dx.doi.org/10.1007/b97624.
  * Bouchaud and Georges [1990] Jean-Philippe Bouchaud and Antoine Georges.  Anomalous diffusion in disordered media: Statistical mechanisms, models and physical applications.  _Physics Reports_ , 195(4-5):127–293, November 1990.  ISSN 03701573.  doi: 10.1016/0370-1573(90)90099-N.
  * Jespersen et al. [1999] Sune Jespersen, Ralf Metzler, and Hans C. Fogedby.  Lévy flights in external force fields: Langevin and fractional Fokker-Planck equations and their solutions.  _Physical Review E_ , 59(3):2736–2745, March 1999\.  ISSN 1063-651X, 1095-3787.  doi: 10.1103/PhysRevE.59.2736.
  * West and Deering [1994] Bruce J. West and William Deering.  Fractal physiology for physicists: Lévy statistics.  _Physics Reports_ , 246(1-2):1–100, October 1994\.  ISSN 03701573.  doi: 10.1016/0370-1573(94)00055-7.