Scale-free topology of e-mail networks. For the Poissonian distribution of a random network

Страницы работы

4 страницы (Word-файл)

Фрагмент текста работы

Scale-free topology of e-mail networks

Holger Ebel,[1] Lutz-Ingo Mielsch, and Stefan Bornholdt

Institut fu¨r Theoretische Physik, Universit¨at Kiel, Leibnizstraße 15, D-24098 Kiel, Germany

(Dated: February 11, 2002)

We study the topology of e-mail networks with e-mail addresses as nodes and e-mails as links using data from server log files. The resulting network exhibits a scale-free link distribution and pronounced small-world behavior, as observed in other social networks. These observations imply that the spreading of e-mail viruses is greatly facilitated in real e-mail networks compared to random


architectures.

PACS numbers: 89.20.Hh, 89.75.Hc, 05.65.+b

Complex networks as the World Wide Web or social networks often do not have an engineered architecture but instead are self-organized by the actions of a large number of individuals. From these local interactions nontrivial global phenomena can emerge as, for example, small-world properties [1] or a scale-free distribution of the degree [2]. These global properties have considerable implications on the behavior of the network under error or attack [3], as well as on the spreading of information or epidemics [4]. Here we report that networks composed of persons connected by exchanged e-mails show both the characteristics of small-world networks and scale-free networks.

The nodes of an e-mail network correspond to e-mail addresses which are connected by a link if an e-mail has been exchanged between them. The network studied here is constructed from log files of the e-mail server at Kiel University, recording the source and destination of every e-mail from or to a student account over a period of 112 days [22]. The resulting network consists of N = 59,912 nodes (including 5,165 student accounts) with a mean degree of < k > = 2.88 and contains several separated clusters with less than 150 nodes and one giant component of 56,969 nodes (mean degree < klarge > = 2.96). The degree distribution n(k), i.e. the distribution of the number k of a node’s next neighbors, obeys a power law

                                        n(k) ∝ k−1.81,                                   (1)

with exponential cut-off (Fig. 1).

Most of the scaling exponents reported so far for the degree distributions of computer and social networks lie in the range of -2.0 to -3.4 [5]. One exception is the social network of co-authorships in high energy physics, for which Newman found an exceptionally small scaling exponent of -1.2 [6]. Similar to our work are studies of networks of phone calls made during one day. These phone-call networks show scale-free behavior of the degree distribution as well, with an exponent of -2.1 [7, 8]. Let us briefly discuss how our result on e-mail networks may be influenced by the measurement process. The sampling of the network has been restricted to one

FIG. 1: Degree distribution of the e-mail network. The double-logarithmic plot of the number of e-mail addresses with which a node exchanged e-mails exhibits a power-law with exponent -1.81 ± 0.10 over two decades. This distribution is used to calculate estimates for the clustering coefficient and the average shortest path length for the entire network (see text).

distinct e-mail server. Therefore, only the degrees of accounts at this server are known exactly. Here, these internal accounts correspond to e-mail addresses of local students, whereas the external nodes are given by all other e-mail addresses. We resolve the degree distribution of internal accounts only (Fig. 2), and find that it can be approximated by a power-law nint(k) ∝ k−1.32 as well (mean degree < kint >= 14.86). Since the degrees of external nodes typically are underestimated, this exponent is smaller than for the whole network. For the same reason, there are fewer nodes with small degree in the distribution of students’ degrees. Note that the cut-off of both distributions is about the same. Therefore, external sources addressing almost all internal nodes (e.g. advertisement or spam) do not bias the degree statistics. Thus, it can be concluded that the e-mail network exhibits scale-free behavior.

Furthermore, the e-mail network shows the properties of a “small

Похожие материалы

Информация о работе