On the computation of entropy production in stationary social networks

Completing their initial phase of rapid growth, social networks are expected to reach a plateau from where on they are in a statistically stationary state. Such stationary conditions may have different dynamical properties. For example, if each message in a network is followed by a reply in opposite direction, the dynamics is locally balanced. Otherwise, if messages are ignored or forwarded to a different user, one may reach a stationary state with a directed flow of information. To distinguish between the two situations, we propose a quantity called entropy production that was introduced in statistical physics as a measure for non-vanishing probability currents in nonequilibrium stationary states. The proposed quantity closes a gap for characterizing online social networks. As major contribution, we show the relation and difference between entropy production and existing metrics. The comparison shows that computational intensive metrics like centrality can be approximated by entropy production for typical online social networks. To compute the entropy production from real-world measurements, the need for Bayesian inference and the limits of naïve estimates for those probability currents are shown. As further contribution, a general scheme is presented to measure the entropy production in small-world networks using Bayesian inference. The scheme is then applied for a specific example of the R mailing list.

\(T\) :

Measurement period over which messages between individuals are recorded

\(n_{ij}\) :

Number of messages sent from \(i\) to \(j\) during time \(T\)

\(N\) :

Total number of individuals, i.e., nodes in the graph, communicating during \(T\)

\(M\) :

Total number of recorded messages, i.e., directed link, \(M=\sum _{i,j=1}^N n_{ij}\)

\(\delta _{a,b}\) :

Kronecker delta defined by \(\delta _{a,b}={\left\{ \begin{array}{ll} 1 &{} a=b \\ 0 &{} a\ne b \end{array}\right. }\)

\(L\) :

Total number of directed links, \(L=\sum _{i,j=1}^N 1-\delta _{0,n_{ij}}\)

\(n_i^{\mathrm{out}}\) :

Number of outgoing messages from node \(i\), \(n_i^{\mathrm{out}}=\sum _{j=1}^N n_{ij}\)

\(n_i^{\mathrm{in}}\) :

Number of incoming messages to node \(i\), \(n_i^{\mathrm{in}}=\sum _{j=1}^N n_{ji}\)

\(d_i^{\mathrm{out}}\) :

Outgoing degree of node \(i\)

\(d_i^{\mathrm{in}}\) :

Incoming degree of node \(i\)

\(d_i\) :

Degree of node \(i\)

\(\Delta n_i\) :

Difference of outgoing and incoming messages of node \(i\)

\(P(n)\) :

Probability that \(n\) messages are sent on a link, \(P(n)= \sum _{i,j=1}^N \delta _{n,n_{ij}}/N(N-1)\)

\(\mathcal {A}\) :

Adjacency matrix with matrix elements \(\mathcal {A}_{ij}=1-\delta _{0,n_{ij}}\)

\(w_{ij}\) :

Message rate from \(i\) to \(j\) estimated by measured \(n_{ij}\) over \(T\)

\(\mathcal {W}\) :

Rate matrix with matrix elements \(\mathcal {W}_{ij}=w_{ij}\)

\(\Delta H_{ij}\) :

Amount of entropy increased for each message sent from \(i\) to \(j\), \(\Delta H_{ij}=\ln \frac{w_{ij}}{w_{ji}}\)

\(H_{ij}\) :

Entropy production per link, \(H_{ij} = \left( n_{ij}-n_{ji}\right) \ln \frac{w_{ij}}{w_{ji}}\)

\(H_i\) :

Entropy production per node \(i\), \(H_i=\frac{1}{2}\sum _{j=1}^N H_{ij}\)

\(H\) :

Entropy production of total network, \(H=\sum _{i=1}^N H_i\)

\(h_i\) :

Node entropy production per message, \(h_i = \frac{H_i}{n_i^{\mathrm{out}}+n_i^{\mathrm{in}}}\)

\(P(w|n)\) :

Posterior distribution of message rates \(w\) conditional on observed messages \(n\)

\(P(w)\) :

Prior distribution of message rates; assumed to follow a power law in social networks with \(P(w) \sim w^{-1-\alpha }\); normalization with suitable lower cutoff leads to inverse gamma distribution \(P(w) \;=\; \frac{\beta ^{\alpha }}{\Gamma (\alpha )} {w^{-\alpha -1} e^{-\beta /w}}\)

\(\alpha\) :

Shape parameter of the inverse gamma distribution

\(\beta\) :

Lower cutoff parameter for the rate \(w\) concerning inverse gamma distribution

\(P(n)\) :

Normalizing marginal likelihood

\(\langle \ln w \rangle _n\) :

Expectation value for given \(n\), \(\langle \ln w \rangle _n \;=\; \int \limits _0^{\infty } \mathrm{d}w\, \ln w P(w|n)\)

\(K_\nu (z)\) :

Modified Bessel function of the second kind and \(z=2\sqrt{\beta T}\)

Authors and Affiliations

1. Chair of Communication Networks, Institute of Computer Science, University of Würzburg, Am Hubland, 97074 , Würzburg, Germany

   Tobias Hoßfeld, Valentin Burger, Matthias Hirth & Phuoc Tran-Gia

2. Department of Physics and Astronomy, University of Würzburg, Am Hubland, 97074 , Würzburg, Germany

   Haye Hinrichsen

Corresponding author

Correspondence to Tobias Hoßfeld.

This article is part of the Topical Collection on Social Systems as Complex Networks.

Reprints and permissions