We study the dynamic network of e-mail traffic and find that it develops self-organized coherent structures similar to those appearing in many nonlinear dynamic systems. Such structures are uncovered by a general information theoretic approach to dynamic networks based on the analysis of synchronization among trios of users. In the e-mail network, coherent structures arise from temporal correlations when users act in a synchronized manner. These temporally linked structures turn out to be functional, goal-oriented aggregates that must react in real time to changing objectives and challenges (e.g., committees at a university). In contrast, static structures turn out to be related to organizational units (e.g., departments). A n intriguing aspect of networks is the appearance of internal structures whose origins cannot be explained by using graph theoretic concepts alone. These are contextual and thematic groups that form by the clustering of nodes with similar properties. Their existence can be detected by various measures of connectivity (1-3), and they have numerous uses in data mining (4). The addition of temporal dynamics can be expected to have a profound effect on the creation of such structures. The time-dependent activation of links creates a flow of information along the static network that, in turn, defines an ever-changing subgraph that can only exist as a consequence of this flow. This flux of activation will concentrate and cluster into structures that act coherently for a given period, then relax and decay until they are excited again. A dynamic network can be defined as a graph whose links are turned on or off by the individual nodes. Prominent examples are the brain, where spikes are exchanged among neurons to create thoughts, and communication networks such as telephones or e-mail. It is convenient to think of the static counterpart as the same graph in which permanent links are made when certain criteria are fulfilled, e.g., when the number of messages transmitted between two nodes exceeds a certain threshold level. The temporal dynamics create coherent space-time structures that involve correlations of the interacting nodes. These (coherent and dynamic) structures will in general be very different from the fixed ones that appear in the static network. E-mail traffic, a fascinating form of communication that increasingly dominates written correspondence, creates such a dynamic network. The resulting graph has intricate structures that are neither apparent to the users nor carried by the content of the messages. The traffic has a precise time stamp on every interaction, which can be used as a ''stroboscopic probe'' to identify the coherent space-time structures that arise. In this work, we measure synchronized interaction among users by looking at communicating triangles of users. We analyze them with the tools of information theory (5) and find a form of organization that differs from that which can be captured by static attributes of the graph such as curvature. A similar approach is often used to find correlations and synchronization of spike trains in the neural code (6), evoking an analogy between the internal e-mail communication in a university and neuronal activity in the brain. Our data were extracted from the log files of one of the main mail servers at one of our universities and consist of Ͼ2 ϫ 10 6 e-mail messages sent during a period of 83 days and connecting Ϸ10,000 users. The content of the messages was, of course, never accessible, and the only data taken from the log files were the ''to,'' ''from,'' and ''time'' fields. The data were first reduced to the internal mail within the institution, because external links were necessarily incomplete. Once aliases were resolved, we were left with a set of 3,188 users interchanging 309,125 messages. A directed static graph was then constructed by designating users as nodes and connecting any two of them with a directed link when an e-mail message had gone between them during the 83 days. Statistical properties of the degree of this graph have been reported before (7). ¶ Connectivity of this static graph will reveal structures within the organization (7-9). We have previously shown (1) that a powerful tool for identifying such structural organization is the number of triangles T (triplets in which all pairs communicate) in which a node of degree v (total number of partners) participates, normalized by the number of triangles v(v Ϫ 1)͞2 to which it could potentially belong. This defines the clustering coefficient c ϭ 2T͞(v 2 Ϫ v) (10-13), which, as we showed (1), induces a curvature on the graph. One marked difference between the graphs of e-mail and of the World Wide Web (WWW) should be noted at this point. In the WWW, the central organizing role of ''hubs'' (nodes with many outgoing links) that confer importance to ''authorities'' (nodes with many ingoing links) has been noted (14) and used very successfully (e.g., by Google). The contribution of authorities and hubs is, however, not to the creation of communities and interest groups. This is evident because the high degree of both hubs and authorities tends to reduce their curvature considerably. High-curvature nodes, in contrast, are usually the specialists of their community and are highly connected in bidirectional links to others in the group. In the e-mail graph, hubs tend to be machines, mass mailers, or users that transfer general messages (e.g., seminar notifications) going to many users, whereas authorities are more like service desks. Thus, the importance of hubs and authorities is small when we consider the core use of the e-mail structure as dealing with thematic rather than organizational issues. Hubs and authorities do, however, play a role in such questions as diffusion of viruses or, more generally, how many people are being reached (7). However, most mass mailings do not solicit an answer and therefore do not contribute to interaction (''dialogue'') as we define and study it here. In our § To whom correspondence should be addressed. E-mail: elisha.moses@weizmann.ac.il. ¶ We have confirmed a scaling law for the number of messages sent MS and the number of messages received MR per user, and we find that both occur with probabilities p(MS,R) Ϸ MS,R Ϫ1.0 Ϯ 0.1 . The degree of the graph, i.e., the degree or number of links going in vin and out of vout a node, does not have a simple scaling behavior. Instead, one power law of v Ϫ0.93 characterizes the behavior of both vin and vout until v ϭ 12, when a sharp transition to a second power law with v Ϫ1.84 fits the behavior until v Ϸ 200, when our data end.
REF observed that activation of links in a dynamic network creates a flow of information that leads to coherent clusters.
Entropy of dialogues creates coherent structures in e-mail traffic
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Computer Science Medicine