Inversion method for content-based networks

In this paper, we generalize a recently introduced expectation maximization (EM) method for graphs and apply it to content-based networks. The EM method provides a classification of the nodes of a graph, and allows one to infer relations between the different classes. Content-based networks are ideal models for graphs displaying any kind of community and/or multipartite structure. We show both numerically and analytically that the generalized EM method is able to recover the process that led to the generation of such networks. We also investigate the conditions under which our generalized EM method can recover the underlying content-based structure in the presence of randomness in the connections. Two entropies, $S_q$ and $S_c$, are defined to measure the quality of the node classification and to what extent the connectivity of a given network is content based. $S_q$ and $S_c$ are also useful in determining the number of classes for which the classification is optimal.

Figure 1

(Color online) An example of a content-based network, the colors and the sizes of the nodes correspond to the different contents (green $A$, red $B$, blue $C$, magenta $D$, cyan $E$, olive $F$, and orange $G$).

Figure 2

(Color online) A simple scenario in which the EM method for directed networks, as defined in [30], has problems in classifying the nodes of the network in two classes. The configurations (a) and (b) are possible outputs of the original EM method since both satisfy the normalization condition of Eq. (6). The solution (a) comes together with values for $q_{ir}=1∕2$ for all the nodes and classes, while the solution (b), which has a lower likelihood, produces $q_{ir}\approx 0.99$ for all the nodes in one class and a very small probability for the other. The plot on the right, solution (c), is the output offered by the generalization of EM with values of $q_{ir}$ virtually one or zero.

Figure 3

(Color online) Connectivity function $c(x,y)$ for the theoretical example of Sec. 5A. The number of contents is six: $A,B,C,D,E$, and $F$. The points represent the ones in the connectivity matrix, the values not marked are zero.

Figure 4

(Color online) Connectivity functions $c(x,y)$ for the two examples of content-based networks analyzed in the simulation sections. The number of contents considered is five, $A,B,C,D$, and $E$. The contents of the connectivity function $\left(\mathcal{A}\right)$ display no cover relation, while in the second example, $\left(\mathcal{B}\right)$, $A\succ B$. The networks are generated assuming equal probability for the five contents at the assignation of a content to each node.

Figure 5

(Color online) An example of classification, the original network is on the top and on the bottom the probability $q_{ir}$ is represented graphically. The color and size of the symbols correspond to the contents of the nodes (green $A$, red $B$, magenta $C$, blue $D$, and cyan $E$). On the bottom, the radius of the spheres is proportional to the probability $q_{ir}$. The network $\mathcal{A}$ is generated using the connectivity function $c_{\mathcal{A}}$ of Fig. 4 with no cover relation among the classes, while on the right we have used $c_{\mathcal{B}}$, which incorporates a single cover relation between $A$ and $B$ such that $A\succ B$.

Figure 6

(Color online) Shown in the lower panels are $S_q$ (circles) and its fluctuations ${\sigma }_S$ (squares) as a function of ${\mathcal{N}}_c$ for the networks of Fig. 5. In order to facilitate visualization, the insets show the same curves in a semilogarithmic plot. The top panels display the same quantities, $S_q$ and ${\sigma }_S$, but ensemble averaged over different realizations of the content-based networks generated with the connectivity function of Fig. 4.

Figure 7

(Color online) On the top, the connectivity function $\tilde{c}(r,s)$ obtained from the EM classification of the networks displayed in Fig. 5. The radii of the circles is proportional to the value of $\tilde{c}(r,s)$. On the bottom, we are showing how $S_c$ goes with ${\mathcal{N}}_c$ for the same networks as well as, in the inset, an average over different content-based realizations generated with the connectivity functions of Fig. 4.

Figure 8

(Color online) Same network as in section $\mathcal{A}$ of Fig. 5 but with increasing error probability $P$. The values of $P$ are from left to right $0.001$, $0.01$, and $0.1$. The plots on the lower panel are a graphic representation of the probability of classifying node $i$ in class $r$, $q_{ir}$, as before the radius of the spheres are proportional to $q_{ir}$ and the colors correspond to the actual content of the nodes (green $A$, red $B$, magenta $C$, blue $D$, and cyan $E$).

Figure 9

The error rate $ϵ$ as a function of the error probability $P$ for content-based networks generated with the connectivity functions of Fig. 4 and with ${\mathcal{N}}_c={\mathcal{N}}_x=5$.

Figure 10

(Color online) The average entropies over different realizations for content-based networks generated with the connectivity functions of Fig. 4. In the top panels, $S_c$ is represented as a function of the number of classes ${\mathcal{N}}_c$ for two different levels of disorder: the circles are $P=1\%$, while the triangles for $P=10\%$. On the bottom panels, $S_q$ and ${\sigma }_S$ versus ${\mathcal{N}}_c$ for the disorder probabilities $P=1\%$, circles $\left(S_q\right)$, and squares $\left({\sigma }_S\right)$, and $P=10\%$, triangles $\left(S_q\right)$, and stars $\left({\sigma }_S\right)$.

Figure 11

(Color online) The average entropy $S_c$ as a function of the disorder probability $P$ for content-based networks generated with the connectivity functions $c_{\mathcal{A}}$ and $c_{\mathcal{B}}$ depicted in Fig. 4. The red curves correspond to the value of $S_c^{*}$.