Abstract The directed L-distance minimal dominating set (MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theoretical interest. We only give results for an Erdós Rényi (ER) random graph and regular random (RR) graph, but this work can be extended to any type of network. We develop spin glass theory to study the directed 2-distance MDS problem. First, we find that the belief propagation (BP) algorithm does not converge when the inverse temperature β exceeds a threshold on either an ER random network or RR network. Second, the entropy density of replica symmetric theory has a transition point at a finite β on a regular random graph when the arc density exceeds 2 and on an ER random graph when the arc density exceeds 3.3; there is no entropy transition point (or $\beta =\infty $) in other circumstances. Third, the results of the replica symmetry (RS) theory are in agreement with those of BP algorithm while the results of the BP decimation algorithm are better than those of the greedy heuristic algorithm. Keywords：directed 2-distance minimal dominating set;belief propagation;regular random graph;ER random graph;belief propagation decimation
PDF (439KB)MetadataMetricsRelated articlesExportEndNote|Ris|BibtexFavorite Cite this article Yusupjan Habibulla. Statistical mechanics of the directed 2-distance minimal dominating set problem. Communications in Theoretical Physics, 2020, 72(9): 095602- doi:10.1088/1572-9494/aba249
1. Introduction
There is a close relationship among the minimal dominating set (MDS), the directed minimal dominating set (DMDS), the L-distance minimal dominating set (L-MDS) and the directed L-distance minimal dominating set (D-LMDS). The idea behind the MDS is to construct the node set of smallest size such that any node of the network is either in this set or is adjacent to at least one node of this set. A DMDS is the smallest set of nodes such that each node either belongs to this set or has at least one parent node in this set. The allocation of network resources that satisfies a given service with the least use of resources is a frequent problem in the field of communication networks. We are interested in the problem of computing the minimum set of occupied nodes (referred to henceforth as servers) such that every node is occupied or has at least one occupied parent node at a distance of at most L (i.e. the L-MDS problem), where the distance between two nodes in the graph is the minimum number of hops necessary to go from one node to the other. Each parent server then provides a service to or monitors those child nodes within a distance L. Consider a simple network W formed by N nodes and M arcs (directed edges), with each arc (i, j) pointing from a parent node (predecessor) i to a child node (successor) j. The arc density α is defined simply as α ≡ M/N. There is a set γ; if any node of the network belongs to this set or at least one parent neighbor node within 2-distance belongs to this set, then this set γ is called D-2MDS of the given network W. If node i belongs to D-2MDS, we say node i is occupied. In figure 1, the green nodes (i.e. occupied nodes) construct D-2MDS for the given small graph. If node i belongs to D-2MDS or at least one parent node within 2-distance is occupied, we then say node i is observed. In the figure, each blue node has at least one occupied parent neighbor node within 2-distance so that it is observed.
Figure 1.
New window|Download| PPT slide Figure 1.Example of the directed 2-distance minimum dominating set. A small network with N=31 nodes and M=30 arcs. Green indicates an occupied node while blue indicates an empty but observed node. The three occupied nodes form a D-2MDS for this network.
The L-MDS problem arises mainly in the design of a communication network in the real world. L-MDS has important applications in several fields; e.g. communication networks [1], locating servers [2] and copying a distributed directory [3]. There are various types of L-MDS problem, such as Liar’s dominating set [4], the extended dominating set [5], the 2-distance paired dominating set [6], the [1, 2]-dominating set [7], the (Σ, ρ ) dominating set [8], and the k-tuple dominating set [9]. The DMDS has wide application in the field of biological networks, such as for the spread of infectious disease [10], genetic regulation [11, 12] and chemical reactions and metabolic regulation [13], and it is also applied in social, information and neuroscience fields [14–19]. If we naturally extend the regular DMDS problem, we get the corresponding D-2MDS problem; e.g. it is a regular DMDS problem in power generation and transportation [20]. If we assume that a power station can transport power to the 2-distance neighbor, then this power supply problem converts to a D-2MDS problem. There have been few works on the D-2MDS problem, and they only consider special cases; e.g. Wang and Chang [21] studied the unique minimum distance dominating set in directed split-stars using distributed algorithms while Banerjee et al [22] introduced the directed d-hop MDS in which the in-degree equals 1.
We adopt spin glass theory in this paper. Spin glass theory has wide application for optimization problems, such as k-sat [23], vertex cover [24], the feedback vertex set problem [25] and dominating set problem. We recently used spin glass theory to study the regular (L=1) MDS problem [26–29]. We introduced belief propagation decimation (BPD), warning propagation and survey propagation decimation algorithms to get the MDS and found that our algorithms rapidly provided solutions close to the optimal solution. This year, we used spin glass theory to study the undirected 2-distance MDS problem [30] and developed a BPD algorithm and greedy algorithm to estimate the size of the 2-distance MDS. In the present paper, we adopt statistical physics to study the D-2MDS, finding that the entropy density of the directed network work like with undirected network. This indicates that the solution spaces of the directed and undirected networks are connected with each other. We use three algorithms, namely population dynamics, BPD and greedy heuristic algorithms, to calculate the D-2MDS and find that the results of population dynamics and BPD algorithms are consistently better than those of the greedy heuristic algorithm on both Erdós Rényi (ER) random networks and regular random (RR) networks.
The remainder of the paper is organized as follows. Section 2 introduces RS theory for the D-2MDS problem and presents the belief propagation (BP) equation and corresponding thermodynamic quantities. Section 3 introduces the BPD and greedy algorithm for the D-2MDS problem, deriving the BP equation and marginal probability equation for the different node state condition. Section 4 summarizes our results and presents conclusions.
2. RS
This section introduces mean-field theory for the D-2MDS problem. The partition function plays an important role, with the entire calculation starting from the partition function. However, deriving the correct partition function is not a simple task. We assume that each node only interacts with its neighbors at the same time, so each node has a constraint on all its neighbor nodes. Depending on the RS mean-field theory of the statistical physics, we write the partition function Z as$ \begin{eqnarray}\begin{array}{rcl}Z & = & \displaystyle \sum _{\underline{c}}\displaystyle \prod _{i\in W}{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}\left\{1-(1-{\delta }_{{c}_{i}}^{0})\displaystyle \prod _{j\in \partial {i}^{+}}(1-{\delta }_{{c}_{j}}^{{c}_{i}-1})\right.\\ & & \left.-{\rm{\Theta }}\left[\left(\displaystyle \sum _{j\in \partial {i}^{+}}{\delta }_{{c}_{j}}^{{c}_{i}-2}+\displaystyle \sum _{j\in \partial {i}^{-}}{\delta }_{{c}_{j}}^{{c}_{i}+2}\right)-1\right]\right\},\end{array}\end{eqnarray}$where the Kronecker symbol ${\delta }_{m}^{n}=1$ if m=n and ${\delta }_{m}^{n}=0$ otherwise while the function Θ(x)=1 if x≥0 and Θ(x)=0 otherwise. The symbol $\underline{c}\equiv ({c}_{1},{c}_{2},\ldots ...,{c}_{n})$ denotes one of the 3n configurations. If node i is in state ci=0, it requests the successors only take state ck=0 or ck=1, and state ck=2 is forbidden, but the predecessors can take any state. If node i is in state ci=1, it allows neighbor nodes to take any state, but at least one predecessor must be occupied. If node i is in state ci=2, it requests the predecessors only take state ck=1 or ck=2, at least one predecessor must be in state ci=1, state ck=0 is forbidden for the predecessors, and successors can take any state. β is the inverse temperature. $\partial {i}^{+}$ denotes all the predecessors of node i while $\partial {i}^{-}$ denotes all the successors of node i. The partition function therefore only takes into account all the directed 2-distance dominating set, and at $\beta \to \infty $ it is contributed exclusively by the D-2MDS configurations.
RS mean-field theories, such as the Bethe–Peierls approximation [26] and partition function expansion [27], give a good estimation of the above spin glass model. These two theories provide the same results. In the present work, we derive the BP equation using the Bethe–Peierls approximation theory. We define on each arc (i, j) of digraph D a distribution function ${p}_{i\to j}^{({c}_{i},{c}_{j})}$, which is the probability of node i being in state ci and node j being in state cj if the constraint of j is not considered, and another distribution function ${p}_{j\leftarrow i}^{({c}_{j},{c}_{i})}$, which is the probability of j being in state cj and i being in state ci if the constraint of i is not considered. These messages must satisfy the equations$ \begin{eqnarray}{p}_{i\leftarrow j}^{({c}_{i},{c}_{j})}=\displaystyle \frac{{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}{A}_{i\leftarrow j}^{({c}_{i},{c}_{j})}}{{\displaystyle \sum }_{{\acute{c}}_{i},{\acute{c}}_{j}}{{\rm{e}}}^{-\beta {\delta }_{{\acute{c}}_{i}}^{0}}{A}_{i\leftarrow j}^{({\acute{c}}_{i},{\acute{c}}_{j})}},\end{eqnarray}$$ \begin{eqnarray}{p}_{i\to j}^{({c}_{i},{c}_{j})}=\displaystyle \frac{{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}{A}_{i\to j}^{({c}_{i},{c}_{j})}}{{\displaystyle \sum }_{{\acute{c}}_{i},{\acute{c}}_{j}}{{\rm{e}}}^{-\beta {\delta }_{{\acute{c}}_{i}}^{0}}{A}_{i\to j}^{({\acute{c}}_{i},{\acute{c}}_{j})}},\end{eqnarray}$$ \begin{eqnarray}\begin{array}{rcl}{A}_{i\leftarrow j}^{({c}_{i},{c}_{j})} & = & \left[\displaystyle \prod _{k\in \partial {i}^{+}\setminus j}\displaystyle \sum _{{c}_{k}\in {A}^{+}}{p}_{k\to i}^{({c}_{k},{c}_{i})}\right.\\ & & \left.-{R}_{i\leftarrow j}^{({c}_{i},{c}_{j})}\displaystyle \prod _{k\in \partial {i}^{+}\setminus j}\displaystyle \sum _{{c}_{k}\geqslant {c}_{i}}{p}_{k\to i}^{({c}_{k},{c}_{i})}\right]\displaystyle \prod _{k\in \partial {i}^{-}}\displaystyle \sum _{{c}_{k}\in {A}^{-}}{p}_{k\leftarrow i}^{({c}_{k},{c}_{i})},\end{array}\end{eqnarray}$$ \begin{eqnarray}{R}_{i\leftarrow j}^{({c}_{i},{c}_{j})}=(1-{\delta }_{{c}_{i}}^{0})({\delta }_{{c}_{j}}^{{c}_{i}}+{\delta }_{{c}_{j}}^{{c}_{i}+1}),\end{eqnarray}$$ \begin{eqnarray}\begin{array}{rcl}{A}_{i\to j}^{({c}_{i},{c}_{j})} & = & \left[\displaystyle \prod _{k\in \partial {i}^{+}}\displaystyle \sum _{{c}_{k}\in {A}^{+}}{p}_{k\to i}^{({c}_{k},{c}_{i})}\right.\\ & & \left.-(1-{\delta }_{{c}_{i}}^{0})\displaystyle \prod _{k\in \partial {i}^{+}}\displaystyle \sum _{{c}_{k}\geqslant {c}_{i}}{p}_{k\to i}^{({c}_{k},{c}_{i})}\right]\displaystyle \prod _{k\in \partial {i}^{-}\setminus j}\displaystyle \sum _{{c}_{k}\in {A}^{-}}{p}_{k\leftarrow i}^{({c}_{k},{c}_{i})}.\end{array}\end{eqnarray}$
These two equations (2) and (3) are collectively referred to as the BP equation. A+ represents the set of possible predecessor states while A− represents the set of possible successor states. The marginal probability pic of node i is expressed as$ \begin{eqnarray}{p}_{i}^{{c}_{i}}=\displaystyle \frac{{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}{A}_{i}^{{c}_{i}}}{\displaystyle \sum _{{\acute{c}}_{i}}{{\rm{e}}}^{-\beta {\delta }_{{\acute{c}}_{i}}^{0}}{A}_{i}^{{\acute{c}}_{i}}},\end{eqnarray}$$ \begin{eqnarray}\begin{array}{rcl}{A}_{i}^{{c}_{i}} & = & \left[\displaystyle \prod _{k\in \partial {i}^{+}}\displaystyle \sum _{{c}_{k}\in {A}^{+}}{p}_{k\to i}^{({c}_{k},{c}_{i})}-(1-{\delta }_{{c}_{i}}^{0})\right.\\ & & \left.\times \displaystyle \prod _{k\in \partial {i}^{+}}\displaystyle \sum _{{c}_{k}\geqslant {c}_{i}}{p}_{k\to i}^{({c}_{k},{c}_{i})}\right]\displaystyle \prod _{k\in \partial {i}^{-}}\displaystyle \sum _{{c}_{k}\in {A}^{-}}{p}_{k\leftarrow i}^{({c}_{k},{c}_{i})}.\end{array}\end{eqnarray}$
We calculate the marginal probability using the converged cavity messages ${p}_{k\to i}^{({c}_{k},{c}_{i})}$ and ${p}_{k\leftarrow i}^{({c}_{k},{c}_{i})}$. pi0 denotes the probability that node i is occupied, pi1 denotes the probability that node i has at least one occupied parent neighbor, and pi2 denotes the probability that node i has at least one occupied 2-distance parent neighbor.
The free energy is finally calculated using mean-field theory as$ \begin{eqnarray}{F}_{0}=\displaystyle \sum _{i=1}^{N}{F}_{i}-\displaystyle \sum _{(i,j)\in G}{F}_{(i,j)},\end{eqnarray}$where$ \begin{eqnarray}\begin{array}{rcl}{F}_{i} & = & -\displaystyle \frac{1}{\beta }\mathrm{ln}\left[\displaystyle \sum _{{c}_{i}}{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}\left[\displaystyle \prod _{k\in \partial {i}^{+}}\displaystyle \sum _{{c}_{k}\in {A}^{+}}{p}_{k\to i}^{({c}_{k},{c}_{i})}\right.\right.\\ & & \left.-(1-{\delta }_{{c}_{i}}^{0})\displaystyle \prod _{k\in \partial {i}^{+}}\displaystyle \sum _{{c}_{k}\geqslant {c}_{i}}{p}_{k\to i}^{({c}_{k},{c}_{i})}\right]\\ & & \left.\times \displaystyle \prod _{k\in \partial {i}^{-}}\displaystyle \sum _{{c}_{k}\in {A}^{-}}{p}_{k\leftarrow i}^{({c}_{k},{c}_{i})}\right],\end{array}\end{eqnarray}$$ \begin{eqnarray}{F}_{(i,j)}=-\displaystyle \frac{1}{\beta }\mathrm{ln}\left[\displaystyle \sum _{{c}_{i},{c}_{j}}{p}_{i\to j}^{({c}_{i},{c}_{j})}{p}_{j\leftarrow i}^{({c}_{j},{c}_{i})}\right],\end{eqnarray}$here, Fi denotes the free energy of function node i and ${F}_{(i,j)}$ denotes the free energy of the edge (i, j). We iterate the BP equation until it converges to one stable point and then calculate the energy density $E=1/N{\sum }_{i}{p}_{i}^{0}$ and the mean free energy $f\equiv F/N$ using equations (7) and (9). The entropy density is calculated as $s=\beta (E-f)$.
We find that when the inverse temperature β is larger than certain threshold value, BP iteration is unable to converge to a fixed point. Figure 2 shows that the BP equation does not converge when β>11.6 on the ER random graph that The arc density α equals 2.5. The entropy density is always positive, and with an increase in inverse temperature, the change rate of entropy becomes smaller and smaller, such that the entropy density reaches the transition point when the inverse temperature is extremely high. We use population dynamics to calculate the ground-state energy of the ER random graph. The energy density reaches a stable oscillation when the inverse temperature exceeds 10 while the entropy density is very close to zero, and we therefore use the average value of the energy density when the inverse temperature exceeds 10 to determine the ground-state energy.
Figure 2.
New window|Download| PPT slide Figure 2.RS and BP results for the D-2MDS problem on the ER random graph with the arc density α=2.5 and N=104 obtained using the BP equation and population dynamics. In subgraphs A, B, and C, the x-axis denotes the inverse temperature β while the y-axis denotes the thermodynamic quantities. In subgraph D, the x-axis denotes the energy density while the y-axis denotes the entropy density.
Figure 3 shows that the population dynamics equation has a transition point of the entropy density on the RR graph when the The arc density α=3.5 while the BP iteration can not converge when the β>8.2, and we thus did not need to average over the population dynamics results in this range. Tables 1 and 2 show that the phase transition temperature βd first decreases and then increases with The arc density α for both ER random and RR networks, but the energy density is always a monotonic decreasing function of The arc density α for these two networks.
Figure 3.
New window|Download| PPT slide Figure 3.RS and BP results for the D-2MDS problem on the RR random graph with the arc density α=3.5 and N=104 obtained using the BP equation and population dynamics. In subgraphs A, B, and C, the x-axis denotes the inverse temperature β while the y-axis denotes the thermodynamic quantity. In subgraph D, the x-axis denotes the energy density while the y-axis denotes the entropy density.
Table 1. Table 1.Inverse temperature βd at the entropy transition point and corresponding energy density for the ER random graph.
In this work, we use two algorithms to construct the solution of the given graph; i.e. the BPD algorithm and greedy algorithm. The greedy algorithm is fast but does not guarantee good results. The BPD algorithm is not as fast but always provides a good estimation for the 2-distance MDS problem.
3.1. BPD algorithm
If a node i is unobserved (i.e. it is empty and no parent neighbor or 2-distance predecessors are occupied), the cavity message ${p}_{i\to j}$ on the arc $(i\to j)$ and the cavity message ${p}_{i\leftarrow j}$ on the arc $(i\leftarrow j)$ between nodes i and j are updated according to equations (2) and (3) By contrast, if node i is empty but observed and it has at least one occupied parent neighbor node, namely ci=1, then this node does not restrict the states of any of its unoccupied parent neighbors. For such a node i, there is no opportunity to take ci=2, and the cavity message ${p}_{i\to j}$ or ${p}_{i\leftarrow j}$ on link (i, j) is then updated according to the equations$ \begin{eqnarray}\begin{array}{l}{p}_{i\leftarrow j}^{({c}_{i},{c}_{j})}\,=\,\displaystyle \frac{{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}(1-{\delta }_{{c}_{i}}^{2}){\displaystyle \prod }_{k\in \partial {i}^{+}\setminus j}{\displaystyle \sum }_{{c}_{k}\in {A}^{+}}{p}_{k\to i}^{({c}_{k},{c}_{i})}{\displaystyle \prod }_{k\in \partial {i}^{-}}{\displaystyle \sum }_{{c}_{k}\in {A}^{-}}{p}_{k\to i}^{({c}_{k},{c}_{i})}}{{\displaystyle \sum }_{{\acute{c}}_{i},{\acute{c}}_{j}}{{\rm{e}}}^{-\beta {\delta }_{{\acute{c}}_{i}}^{0}}(1-{\delta }_{{c}_{i}}^{2})[{\displaystyle \prod }_{k\in \partial {i}^{+}\setminus j}{\displaystyle \sum }_{{\acute{c}}_{k}\in {A}^{+}}{p}_{k\to i}^{({\acute{c}}_{k},{\acute{c}}_{i})}{\displaystyle \prod }_{k\in \partial {i}^{-}}{\displaystyle \sum }_{{\acute{c}}_{k}\in {A}^{-}}{p}_{k\to i}^{({\acute{c}}_{k},{\acute{c}}_{i})}},\end{array}\end{eqnarray}$$ \begin{eqnarray}\begin{array}{l}{p}_{i\to j}^{({c}_{i},{c}_{j})}\,=\,\displaystyle \frac{{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}(1-{\delta }_{{c}_{i}}^{2}){\displaystyle \prod }_{k\in \partial {i}^{+}}{\displaystyle \sum }_{{c}_{k}\in {A}^{+}}{p}_{k\to i}^{({c}_{k},{c}_{i})}{\displaystyle \prod }_{k\in \partial {i}^{-}\setminus j}{\displaystyle \sum }_{{c}_{k}\in {A}^{-}}{p}_{k\to i}^{({c}_{k},{c}_{i})}}{{\displaystyle \sum }_{{\acute{c}}_{i},{\acute{c}}_{j}}{{\rm{e}}}^{-\beta {\delta }_{{\acute{c}}_{i}}^{0}}(1-{\delta }_{{c}_{i}}^{2}){\displaystyle \prod }_{k\in \partial {i}^{+}}{\displaystyle \sum }_{{\acute{c}}_{k}\in {A}^{+}}{p}_{k\to i}^{({\acute{c}}_{k},{\acute{c}}_{i})}{\displaystyle \prod }_{k\in \partial {i}^{-}\setminus j}{\displaystyle \sum }_{{\acute{c}}_{k}\in {A}^{-}}{p}_{k\to i}^{({\acute{c}}_{k},{\acute{c}}_{i})}}.\end{array}\end{eqnarray}$
For node $i({c}_{i}=1)$, at least one parent neighbor node j is occupied and a message is sent to node i as ${p}_{j\to i}^{(0,0)}={p}_{j\to i}^{(0,1)}=0.5$. This leads to ${p}_{j\to i}^{(0,1)}+{p}_{j\to i}^{(1,1)}+{p}_{j\to i}^{(2,1)}\,={p}_{j\to i}^{(0,1)}$, such that the constraints of node i on all other predecessors are automatically removed. The marginal probability is calculated as$ \begin{eqnarray}\begin{array}{l}{p}_{i}^{{c}_{i}}\,=\,\displaystyle \frac{{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}(1-{\delta }_{{c}_{i}}^{2}){\displaystyle \prod }_{k\in \partial {i}^{+}}{\displaystyle \sum }_{{c}_{k}\in {A}^{+}}{p}_{k\to i}^{({c}_{k},{c}_{i})}{\displaystyle \prod }_{k\in \partial {i}^{-}}{\displaystyle \sum }_{{c}_{k}\in {A}^{-}}{p}_{k\to i}^{({c}_{k},{c}_{i})}}{{\displaystyle \sum }_{{\acute{c}}_{i}}{{\rm{e}}}^{-\beta {\delta }_{{\acute{c}}_{i}}^{0}}(1-{\delta }_{{c}_{i}}^{2}){\displaystyle \prod }_{k\in \partial {i}^{+}}{\displaystyle \sum }_{{\acute{c}}_{k}\in {A}^{+}}{p}_{k\to i}^{({\acute{c}}_{k},{\acute{c}}_{i})}{\displaystyle \prod }_{k\in \partial {i}^{-}}{\displaystyle \sum }_{{\acute{c}}_{k}\in {A}^{-}}{p}_{k\to i}^{({\acute{c}}_{k},{\acute{c}}_{i})}}.\end{array}\end{eqnarray}$
If node i is empty but observed (i.e. it has no adjacent occupied parent node but has one occupied 2-distance predecessor), then this node does not restrict the occupation state of any of its unoccupied parent neighbors. For such a node i, the output message ${p}_{i\to j}$ or ${p}_{i\leftarrow j}$ on link (i, j) is then updated according to$ \begin{eqnarray}{p}_{i\leftarrow j}^{({c}_{i},{c}_{j})}=\displaystyle \frac{{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}{A}_{i\leftarrow j}^{({c}_{i},{c}_{j})}}{{\displaystyle \sum }_{{\acute{c}}_{i},{\acute{c}}_{j}}{{\rm{e}}}^{-\beta {\delta }_{{\acute{c}}_{i}}^{0}}{A}_{i\leftarrow j}^{({c}_{i},{c}_{j})}},\end{eqnarray}$where the function ${A}_{i\leftarrow j}^{({c}_{i},{c}_{j})}$ is defined by equation (4) while ${R}_{i\leftarrow j}^{({c}_{i},{c}_{j})}$ is redefined as$ \begin{eqnarray}{R}_{i\leftarrow j}^{({c}_{i},{c}_{j})}={\delta }_{{c}_{i}}^{1}({\delta }_{{c}_{j}}^{{c}_{i}}+{\delta }_{{c}_{j}}^{{c}_{i}+1}),\end{eqnarray}$$ \begin{eqnarray}{p}_{i\to j}^{({c}_{i},{c}_{j})}=\displaystyle \frac{{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}{A}_{i\to j}^{({c}_{i},{c}_{j})}}{\displaystyle \sum _{{\acute{c}}_{i},{\acute{c}}_{j}}{{\rm{e}}}^{-\beta {\delta }_{{\acute{c}}_{i}}^{0}}{A}_{i\to j}^{({\acute{c}}_{i},{\acute{c}}_{j})}},\end{eqnarray}$$ \begin{eqnarray}\begin{array}{rcl}{A}_{i\to j}^{({c}_{i},{c}_{j})} & = & \left[\displaystyle \prod _{k\in \partial {i}^{+}}\displaystyle \sum _{{c}_{k}\in {A}^{+}}{p}_{k\to i}^{({c}_{k},{c}_{i})}-{\delta }_{{c}_{i}}^{1}\displaystyle \prod _{k\in \partial {i}^{+}}\displaystyle \sum _{{c}_{k}\geqslant {c}_{i}}{p}_{k\to i}^{({c}_{k},{c}_{i})}\right]\\ & & \times \displaystyle \prod _{k\in \partial {i}^{-}\setminus j}\displaystyle \sum _{{c}_{k}\in {A}^{-}}{p}_{k\to i}^{({c}_{k},{c}_{i})}.\end{array}\end{eqnarray}$
For node $i({c}_{i}=2)$, if at least one parent neighbor node j takes the state cj=1, then it sends a message to node i as ${p}_{j\to i}^{(2,1)}={p}_{j\to i}^{(2,2)}=0$. This leads to ${p}_{j\to i}^{(1,2)}+{p}_{j\to i}^{(2,2)}={p}_{j\to i}^{(1,2)}$, and the constraint of node i on all other predecessors is automatically removed. The marginal probability is calculated as$ \begin{eqnarray}{p}_{i}^{{c}_{i}}=\displaystyle \frac{{{\rm{e}}}^{-\beta {\delta }_{{c}_{i}}^{0}}{A}_{i}^{{c}_{i}}}{{\displaystyle \sum }_{{\acute{c}}_{i}}{{\rm{e}}}^{-\beta {\delta }_{{\acute{c}}_{i}}^{0}}{A}_{i}^{{\acute{c}}_{i}}},\end{eqnarray}$$ \begin{eqnarray}\begin{array}{rcl}{A}_{i}^{{c}_{i}} & = & \left[\displaystyle \prod _{k\in \partial {i}^{+}}\displaystyle \sum _{{c}_{k}\in {A}^{+}}{p}_{k\to i}^{({c}_{k},{c}_{i})}-{\delta }_{{c}_{i}}^{1}\displaystyle \prod _{j\in \partial {i}^{+}}\displaystyle \sum _{{c}_{j}\geqslant {\acute{c}}_{i}}{p}_{j\to i}^{({c}_{j},c)}\right]\\ & & \times \displaystyle \prod _{k\in \partial {i}^{-}}\displaystyle \sum _{{c}_{k}\in {A}^{-}}{p}_{k\to i}^{({c}_{k},{c}_{i})}.\end{array}\end{eqnarray}$
We implement the BPD algorithm as follows.(1) Input network W, set all nodes to be unobserved and set all cavity messages ${p}_{i\to j}^{({c}_{i},{c}_{j})}$ and ${p}_{i\leftarrow j}^{({c}_{i},{c}_{j})}$ to be uniform messages. Set the inverse temperature β to a sufficiently large value (depending on the highest convergence inverse temperature). Then perform the BP iteration a number T of rounds (e.g. T=500). Finally, compute the occupation probability of each node i using equation (7). (2) Cover the small fraction γ (e.g. γ=0.01) of the unfixed nodes having highest covering probabilities. (3) Update the state of all unoccupied nodes: if node i is unoccupied and has at least one parent neighbor that takes state ci=0, then it takes state ci=1, while if node i is unoccupied and has no occupied parent neighbor, but has at least one parent neighbor that takes state ci=1, then it takes state ci=2. (4) Fix the state of the observed node; i.e. if the observed node ci=1 has at most one successor taking the state ck=2, then fix the state of node i as ci=1. (5) If network W still contains unobserved nodes, then repeat operations (2)–(4) until all nodes are observed.
During the decimation process, if the remaining graph still contains unobserved nodes, at least one node is moved to the D-2MDS to reduce the number of unobserved nodes. The BPD process terminates only when no unobserved nodes are present in the remaining graph. We implemented the above BPD algorithm using the programming language C++. In our numerical simulations, we set the BPD parameters to be T=500 and γ=0.01. These parameters are not necessarily optimal but are chosen so that a single run of the BPD algorithm on a large graph instance of N=104 nodes and M=105 edges terminates within several minutes. If the fraction γ is further reduced, say to γ=0.001, then the BPD algorithm reaches a slightly smaller D-2MDS, but the computing time is much longer. The complexity of the BP algorithm is $O({{TNd}}_{\max }^{2})$ or $O({{TMd}}_{\max })$ while that of the BPD algorithm is ${\rm{MAX}}[O({TN}\mathrm{log}(N)),O({{TMd}}_{\max })]$, where dmax denotes the maximal node degree of the given network.
3.2. Greedy algorithm
We adopted a simple greedy algorithm from the literature to solve the D-2MDS problem approximately. This algorithm is based on the concept of the general impact of a node. The general impact of an unoccupied node i equals the sum of the impact of all successors that are not occupied. The impact of an unoccupied node i equals the number of child nodes that will be observed by occupying node i. Starting from an input network W with all nodes unobserved, the greedy algorithm selects uniformly at random a node i from the subset of nodes with the highest general impact and fixes its occupation state to ci=0. All successors and 2-distance successors of i are then observed. The state of observed nodes is fixed in step (4) of the BPD implementation process. If there are still unobserved nodes in the network, the impact and general impact values for each of the unoccupied nodes are updated and the greedy occupying process is repeated until all nodes are observed. This pure greedy algorithm is easy and fast to implement, and we find that it usually gives results similar to those of the BPD algorithm when the The arc density α of the given network exceeds 10.
The results of the greedy algorithm for the ER random network and RR network are compared with the results of the BPD algorithm in figures 4 and 5. The BPD algorithm outperforms the greedy algorithm and provides results that are close to those of RS theory on both the ER random and RR graphs.
Figure 4.
New window|Download| PPT slide Figure 4.BPD, RS and greedy algorithm results for the D-2MDS problem on the ER random graph with a size of N=104 nodes. The BPD and greedy algorithm results are obtained on five ER random graphs that include N=104 nodes. The x-axis denotes the The arc density α while and y-axis denotes the energy density. Inverse temperature β=10.0.
Figure 5.
New window|Download| PPT slide Figure 5.BPD, Greedy and RS results for the D-2MDS problem on the RR random graph with a size of N=104 nodes. The x-axis denotes the The arc density α while the y-axis denotes the energy density. Inverse temperature β=10.0.
4. Discussion
We proposed two algorithms (i.e. a greedy-impact local algorithm and a BPD message-passing algorithm) and presented an RS mean-field theory for solving the D-2MDS problem algorithmically and theoretically. We found that the BP and RS algorithms lead to an entropy transition (from a positive value to a negative value) on both ER and RR networks when the The arc density α exceeds a threshold but there is no entropy transition when the The arc density α is lower than this threshold value (i.e. a value of 2 for the RR network and 3.3 for the ER random network). The reason for this result is that the solution space of the D-2MDS problem on the two networks has a structural transition. We will use one-step RS breaking theory to study the solution space of the D-2MDS problem. Our numerical results shown in figures 4 and 5 suggest that the mean-field BPD algorithm constructs a near-optimal D-2MDS for random networks and the mean-field BPD algorithm is better than the greedy algorithm.
There is much theoretical work remaining to be done. We will soon work on the one-step RS breaking of the D-2MDS problem. A more challenging and common problem for the dominating set is the directed connected dominating set problem, and we will use spin glass theory [25] to study the directed minimally connected dominating set problem and the directed 2-distance minimally connected dominating set problem.
Acknowledgments
This research was supported by the doctoral startup fund of Xinjiang University of China (grant number 208-61357) and the National Natural Science Foundation of China (grant number 11 465 019, 11 664 040).
PelegD1991Distributed data structures: a complexity-oriented view Proc. 4th Int. Workshop on Distributed Algorithms Bari, Italy Berlin Springer 7189 DOI:10.1007/3-540-54099-7_6 [Cited within: 1]
WuJCardeiMDaiF et al. 2006 Extended dominating set and its Ap- plications in Ad hoc networks using cooperative communication IEEE Trans. Parallel Distrib. Syst. 17 851864 DOI:10.1109/TPDS.2006.103 [Cited within: 1]
IqbalTBokharyS A U H2019 Paired domination and 2- distance paired domination of the flower graph ${f}_{n\times m}$ (arXiv:1907.01210) [Cited within: 1]
WangH et al. 2014Minimum dominating sets in cell cycle specific protein interaction networksProc. of Int. Conf. on Bioinformatics and Biomedicine (BIBM 2014) Piscataway, NJ IEEE 2530 DOI:10.1109/BIBM.2014.6999122 [Cited within: 1]
WangY JWongG Y1987 Stochastic blockmodels for directed graphs J. Am. Stat. Assoc. 82 819 DOI:10.1080/01621459.1987.10478385
KrauseA E et al. 2003 Compartments revealed in food-web structure Nature 426 282285 DOI:10.1038/nature02115
Guimer`aRStoufferD BSales-PardoMLeichtE ANewmanM E JAmaralL A N2010 Origin of compartmentalization in food webs Ecology 91 29412951 DOI:10.1890/09-1175.1
CahalaneD JClancyBKingsburyM AGrafESpornsOFinlayB L2011 Network structure implied by initial axon outgrowth in rodent cortex: empirical measurement and models PLoS One 6 e16113 DOI:10.1371/journal.pone.0016113
PanR KChatterjeeNSinhaS2010 Mesoscopic organization reveals the constraints governing Caenorhabditis elegans nervous system PLoS One 5 e9240 DOI:10.1371/journal.pone.0009240 [Cited within: 1]
WangF H et al. 2003 Distributed algorithms for finding the unique minimum distance dominating set in directed split-stars J. Parallel Distrib. Comput. 63 481487 DOI:10.1016/S0743-7315(03)00040-6 [Cited within: 1]
BanerjeeJDasASenA2014 Analysis of d-Hop dominating set problem for directed graph with indegree bounded by one (arXiv:1404.6890) [Cited within: 1]
LiKMaHZhouH2009 From one solution of a 3-satisfiability formula to a solution cluster: frozen variables and entropy Phys. Rev. E 79 031102 DOI:10.1103/PhysRevE.79.031102 [Cited within: 1]
HabibullaYZhaoJ HZhouH J2015 The directed dominating set problem: generalized leaf removal and belief propagation Int. Workshop on Frontiers in Algorithmics 9130 Lect. Notes Comput. Sci.7888 DOI:10.1007/978-3-319-19647-3_8 [Cited within: 1]
HabibullaY2017 Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics J. Stat. Mech.103402 DOI:10.1088/1742-5468/aa8c1e
HabibullaY2018 Directed dominating set problem studied by cavity method: warning propagation and population dynamics Commun. Theor. Phys. 70 139148 DOI:10.1088/0253-6102/70/6/785 [Cited within: 1]
HabibullaYQinS M2019 Spin glass approach to the 2-distance minimal dominating set problem (arXiv:1910.07933) [Cited within: 1]
,School of Physics and Technology, 
New window|Download| PPT slide
New window|Download| PPT slide
New window|Download| PPT slide
New window|Download| PPT slide
New window|Download| PPT slide
