Complex networks such 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͔. In smallworld networks short paths between almost any two sites exist even though nodes are highly clustered like in a regular lattice. Scale-free networks are characterized by a power-law distribution of a node's degree, defined as the number of its next neighbors, meaning that structure and dynamics of the network are strongly affected by nodes with a great number of connections. These global properties have considerable implications on the behavior of the network under error or attack ͓3͔, when random or highly connected nodes are destroyed, as well as on the spreading of information or epidemics ͓4 -6͔. The highly connected ''hub'' nodes of a scalefree network and the short paths in a strongly clustered small world greatly facilitate the propagation of an infection over the whole network, which has to be taken into account for designing effective vaccination strategies ͓7-9͔. 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. 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 ͓10͔. 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 ͓11͔. 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 ͓12,13͔. The scale-free e-mail network. The e-mail 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 ͓25͔. The nodes of the e-mail network correspond to e-mail addresses which are connected by a link if an e-mail has been exchanged between them. The resulting network consists of Nϭ59 812 nodes ͑including 5165 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 ͗k giant ͘ϭ2.96). The distribution of the degree k obeys a power law n͑k ͒ϰk , ͑1͒ with exponential cutoff ͑Fig. 1͒. 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 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 n int (k) ϰk Ϫ1.32 as well ͑mean degree ͗k int ͘ϭ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 more nodes with small degree in the distribution of the whole network ͑Fig. 1͒ than in the distribution restricted to internal nodes ͑Fig. 2͒. Note that the cutoff 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. The doublelogarithmic 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͒.
They made use of the very low percolation threshold caused by power-law degree distribution in the e-mail network studied in REF to perform a percolation search and detect arrivals of previously seen spam on the network.
Scale-free topology of e-mail networks
Phys. Rev. E 66 (2002) 035103(R)
Medicine Physics