On zero-error codes produced by greedy algorithms

Let \(G=(V,E)\) be a graph. The number of vertices and edges of G we often denote by n and m, respectively, thus \(|V(G)|=n\) and \(|E(G)|=m\). If \(u,v \in V(G)\) and \(\{u, v\} \in E(G)\), then we say that u is adjacent to v and we write \(u \sim v\). The open neighborhood of a vertex \(v \in V(G)\) is \(N_G(v)=\{u \in V(G):\{u,v\} \in E(G)\}\), and its closed neighborhood is the set \(N_G[v]=N_G(v)\cup \{v\}\). The degree of a vertex v, denoted by \(d_G(v)\), is the cardinality of its open neighborhood. The minimum and maximum degree of G is the minimum and maximum degree among the vertices of G and is denoted by \(\delta (G)\) and \(\varDelta (G)\), respectively. A graph G is regular if \(\delta (G)=\varDelta (G)\). By the complement of G, denoted by \(\overline{G}\), we mean a graph which has the same vertices as G, and two vertices of \(\overline{G}\) are adjacent if and only if they are not adjacent in G. If U is a subset of vertices of G, we write G[U] and \(G-U\) for \((U,E(G) \cap [U]^2)\) and \(G[V(G) {\setminus } U]\), respectively. Furthermore, if \(U = \{v\}\), then we write \(G-v\) rather than \(G-\{v\}\).

Given two graphs \(G_1 = (V(G_1),E(G_1))\) and \(G_2 = (V(G_2),E(G_2))\), the strong product \(G_1 \boxtimes G_2\) is defined as follows. The vertices of \(G_1 \boxtimes G_2\) are all pairs of the Cartesian product \(V(G_1) \times V(G_2)\). There is an edge between \((v_1,v_2)\) and \((u_1,u_2)\) if and only if \(\{v_1,u_1\} \in E(G_1)\) and \(\{v_2,u_2\} \in E(G_2)\), or \(v_1 = u_1\) and \(\{v_2,u_2\} \in E(G_2)\), or \(v_2 = u_2\) and \(\{v_1,u_1\} \in E(G_1)\). The union \(G_1 \cup G_2\) is defined as \((V(G_1) \cup V(G_2),E(G_1) \cup E(G_2))\). In addition, if \(\circ \) is a binary graph operation, then we write \(G^{\circ r}\) to denote the rth power of G, i.e., \(G\circ G\circ \cdots \circ G\), where G occurs r-times.

A clique (independent vertex set, resp.) in a graph \(G=(V,E)\) is a subset \(V' \subseteq V\) such that all (no, resp.) two vertices of \(V'\) are adjacent. The size of a largest clique (independent vertex set, resp.) in a graph G is called the clique (independence, resp.) number of G and is denoted by \(\omega (G)\) (\(\alpha (G)\), resp.). A split graph is one whose vertex set can be partitioned as the disjoint union of an independent set and a clique. A legal coloring of a graph G is an assignment of colors to the vertices of G (\(C:V(G) \rightarrow \mathbb {N})\) such that any two adjacent vertices are colored differently.

A discrete channel W: \(\mathcal {X}\rightarrow \mathcal {Y}\) (or simply W) is defined as a stochastic matrix¹ whose rows are indexed by the elements of a finite input set \(\mathcal {X}\) while the columns are indexed by a finite output set \(\mathcal {Y}\). The (x, y)th entry is the probability W(y|x) that y is received when x is transmitted. A sequence of channels \(\{W^n :\mathcal {X}^n \rightarrow \mathcal {Y}^n \}^\infty _{n=1}\), where \(W^n :\mathcal {X}^n \rightarrow \mathcal {Y}^n\) is the nth direct power of W, i.e.,and \(\mathcal {X}^n\) is the nth Cartesian power of \(\mathcal {X}\), is called a discrete memoryless channel (DMC) with stochastic matrix W and is denoted by \(\{W :\mathcal {X} \rightarrow \mathcal {Y}\}\) or simply \(\{W\}\). See Shannon (1956), Csiszár and Körner (2011), Körner and Orlitsky (1998), Cover and Thomas (2006) and McEliece (2004) for more details.

Let \(W :\mathcal {X} \rightarrow \mathcal {Y}\) be a discrete channel. We define the \(\omega \)-characteristic graph G of W as follows. Its vertex set is \(V(G)=\mathcal {X}\) and its set of edges E(G) consists of input pairs that cannot result in the same output, namely, pairs of orthogonal rows of the matrix W. We define \(\alpha \)-characteristic graph G(W) (we call it characteristic graph for short) of W as the complement of the \(\omega \)-characteristic graph of W. Let \(\{W :\mathcal {X} \rightarrow \mathcal {Y}\}\) be a DMC and so \(W :\mathcal {X} \rightarrow \mathcal {Y}\) is the corresponding discrete channel. We define the characteristic graph \(G(\{W\})\) of the discrete memoryless channel \(\{W\}\) as \(\{G(W^n)\}^\infty _{n=1}\). The Shannon (zero-error) capacity \(C_0(W)\) of the DMC \(\{W :\mathcal {X} \rightarrow \mathcal {Y}\}\) is defined as C(G(W)), whereSee Csiszár and Körner (2011), Körner and Orlitsky (1998), Cover and Thomas (2006) and McEliece (2004) for more details. Let G be the characteristic graph of W and \(\Theta (G)=\sup _{n \in \mathbb {N}}\root n \of {\alpha (G^{\boxtimes n})}\). Then \(\Theta (G)\) uniquely determines \(C_0(W)\).

Let \(W :\mathcal {X} \rightarrow \mathcal {Y}\) be a discrete channel with the characteristic graph G. A sequence of input letters is called an input word. Input words \(x_1x_2 \ldots x_n \in \mathcal {X}^n\) and \(x'_1x'_2 \ldots x'_n \in \mathcal {X}^n\) are orthogonal if the vectors \(W^n(\cdot |x_1x_2 \ldots x_n)\) and \(W^n(\cdot |x'_1x'_2 \ldots x'_n)\) are orthogonal. A zero-error code of block length n for a DMC is defined by a set of mutually orthogonal input words (Körner and Orlitsky 1998; Cover and Thomas 2006). Furthermore, an independent set I of the characteristic graph \(G(W^n)\) corresponds to the zero-error code for \(W^n\) and \(G(W^n)\) is the same as \(G^{\boxtimes n}\) (Shannon 1956; Körner and Orlitsky 1998).

The research on zero-error codes was initiated by Shannon in 1956. He found capacities of a class of channels (graphs) that does not yield additional information benefits (Shannon 1956) and he provided a method which enables constructing codes for these channels. The research was continued by, among others, Lovász (1979) in his IEEE Information Theory Society award work, in which he determined the values of Shannon capacities for some channels with effective codes using the so-called Lovász function. The class of channels examined by Lovász is represented by the so-called vertex-transitive, self-complementary graphs. It is the only one class containing channels with effective codes, for which the an explicit formula of the Shannon capacity is known.

Recently, Polak and Schrijver (2019) and Mathew and Östergård (2017) made some progress in research on channels represented by strong powers of cycles. Moreover, Boche and Deppe (2020) proved that the zero-error capacity is uncomputable in the Banach–Mazur and Borel–Turing senses. Earlier, Alon and Lubetzky (2006) showed that the series of independence numbers of strong powers of a fixed graph can exhibit a complex and unpredictable structure. In this article, we propose polynomial algorithms that approximate the capacity for some channels.

In the next section, we describe the so-called fractional independence number defined by Rosenfeld (1967), which is strongly related to the considered problem.

Computing the independence number of a graph \(G=(V,E)\) can be formulated by the following integer program.where \(S=\{0,1\}\). Now let \(S=[0,1]\). Given a graph G, by \(\alpha _2^{*}(G)\) we denote the optimum of the objective function in the integer program (1). However, for a graph G and a set of not necessarily all its cliques²\(\mathcal {C}\) by \(\alpha _\mathcal {C}^*(G)\) we denote the optimum of the objective function in the following integer program.If \(\mathcal {C}\) is the set of all maximal cliques of size at most r in G, then we denote \(\alpha _\mathcal {C}^*(G)\) by \(\alpha _r^*(G)\). If \(\mathcal {C}\) contains the set of all cliques (or equivalently all maximal cliques) of G, then we denote \(\alpha _\mathcal {C}^*(G)\) by \(\alpha ^*(G)\) and it is called the fractional independence number of G. It is worth to note that \(\alpha ^*\) is multiplicative with respect to the strong product (Scheinerman and Ullman 2011).

The following results present some properties of the linear program (2). In particular, the first observation establishes an order between the above-mentioned measures.

It is interesting that the measure \(\alpha ^*\) has a particular interpretation in information theory (Shannon 1956; Körner and Orlitsky 1998).

It is well known (Shannon 1956) that⁴for each positive integer i. A graph G is of type I if \(\Theta (G)=\alpha (G)\), otherwise is of type II. Furthermore, Hales (1973) showed that for arbitrary graphs G and H we haveIn contrast to the above results, in the next section we use the fractional independence number to calculate lower bounds on the Shannon capacity and the independence number of strong products.

A function \(\beta :\mathcal {G} \rightarrow \mathbb {R}\) is supermultiplicative (resp. submultiplicative) on \(\mathcal {G}\) with respect to the operation \(\circ \), if for any two graphs \(G_1, G_2 \in \mathcal {G}\) we have \(\beta (G_1 \circ G_2) \geqslant \beta (G_1) \cdot \beta (G_2)\) (resp. \(\beta (G_1 \circ G_2) \leqslant \beta (G_1) \cdot \beta (G_2)\)). A supermultiplicative and submultiplicative function is called multiplicative. The independence number \(\alpha \) is supermultiplicative on the set of all graphs with respect to the strong product, i.e., \(\alpha (G \boxtimes H) \geqslant \alpha (G)\cdot \alpha (H)\) for any graphs G and H. Let B be a lower bound on the independence number \(\alpha \), i.e., \(\alpha (G) \geqslant B(G)\). If \(B(G^{\boxtimes i}) > (\alpha (G))^i\) \((i \geqslant 2)\), then G is of type II and is more interesting from an information theory point of view (Shannon 1956). It is possible if \(B(G^{\boxtimes i}) > (B(G))^i\). Thus we require that B has the last two properties for at least one graph, i.e., B recognizes some graphs of type II.

The residue R of a graph G of degree sequence \(S: d_1 \geqslant d_2 \geqslant d_3 \cdots \geqslant d_n\) is the number of zeros obtained by the iterative process consisting of deleting the first term \(d_1\) of S, subtracting 1 from the \(d_1\) following ones, and re-sorting the new sequence in non-increasing order (Favaron et al. 1993). It is well known (Favaron et al. 1991) that \(\alpha (G) \geqslant R(G)\). Unfortunately, the following negative result holds.

We conjecture that the residue is submultiplicative on the set of all graphs with respect to the strong product. This probably means that the residue does not recognize any graphs of type II. There are more such bounds, e.g., the average distance (Jurkiewicz 2017), the Caro–Wei bound and the Wilf bound (Jurkiewicz and Pikies 2015). On the other hand, it is hard to find bounds that recognize at least one graph of type II.

In this section, we analyze, in the context of DMCs codes, the so-called greedy algorithm Min (Algorithm 5.1) that determines an independent set and a lower bound on the independence number of a graph (Harant and Schiermeyer 2001). The algorithm Min has complexity \(O(n^2)\). Similar greedy algorithms can be found in literature (Borowiecki and Rautenbach 2015).

A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution (Cormen et al. 2009). Vertices chosen (in such a way) by Min often strongly block an eventual choice of vertices in a further stage of the algorithm, making generated independent sets are small, especially for strong products of graphs of type II. In Table 1, we summarize results produced by Min for these graphs. On the other hand, Min works well for strong products of investigated graphs of type I. Although channels represented by graphs of type I do not yield additional information benefits, we also need a fast method that determines zero-error codes for these channels. There are at least two ways to do this, i.e., we can run Min on the characteristic graph G of a channel (since \(I^n\) is an independent set of \(G^{\boxtimes n}\) if I is an independent set of G) or directly on a strong power of G. In Table 2, we summarize our results produced by Min for some graphs of type I. It is important to note that, for all results, we randomly⁶ chose vertices with the smallest degrees in Min (in line 4).

In this section, we present a new greedy algorithm that produces an independent set (a DMC code) and a lower bound on the independence number of a strong product. This value, from (5), also determines a lower bound on the Shannon capacity.

A semigroup is a set S with an associative binary operation on S. A semiring is defined as an algebra \((S,+,\cdot )\) such that \((S,+)\) and \((S,\cdot )\) are semigroups and for any \(a,b,c \in S\) we have \(a \cdot (b + c) = a \cdot b + a \cdot c\), \((b + c) \cdot a = b \cdot a + c \cdot a\) (Adhikari and Adhikari 2014). Note that \((\mathcal {G},\cup ,\boxtimes )\) is a semiring, where \(\mathcal {G}\) is the set of all finite graphs. In addition, \(\cup \) and \(\boxtimes \) are commutative operations with neutral elements \((\emptyset ,\emptyset )\) and \(K_1\), respectively.

The considered modification of the greedy algorithm takes as input arbitrary graphs \(G_1,G_2,\ldots ,G_r\) and produces as output an independent set of \(G^\boxtimes =G_1 \boxtimes G_2 \boxtimes \ldots \boxtimes G_r\). From Lemma 2, we can find connected components of \(G^\boxtimes \). Hence, our greedy algorithm can be applied to each connected component of \(G^\boxtimes \) separately, or to the entire graph \(G^\boxtimes \) at once. We prefer the first method.

The next step of our modification is a reduction of factors of a strong product. For each \(i \in \{1,2,\ldots ,r\}\) and any \(u,v \in V(G_i)\), if \(N_{G_i}[u] \subseteq N_{G_i}[v]\), then \(\alpha (G_1 \boxtimes G_2 \boxtimes \ldots \boxtimes G_i \boxtimes \ldots \boxtimes G_r)=\alpha (G_1 \boxtimes G_2 \boxtimes \ldots \boxtimes (G_i-v) \boxtimes \ldots \boxtimes G_r)\) (Jurkiewicz 2020). Let G be a factor of a strong product \(G^\boxtimes \), for example \(G=G_i\). Let > be a strict total order on V(G). We reduce the factor G by Algorithm 6.1 (Reduction GR), which has complexity \(O(\varDelta ^2m)\). This algorithm is correct (in the considered context) since we remove vertices from the strong product, and hence we can only decrease or leave unchanged its independence number.

For some graphs, which we take as input, e.g., for a path on \(n \geqslant 6\) vertices, we need to recursively repeat (at most n times) the algorithm GR to get a smaller graph. Sometimes, the algorithm GR produces vertices with degree zero. Such vertices should be removed from a graph, but taken into account in the outcome.

Let G be a graph and k be a positive integer. Let A be a k-tuple of subsets of V(G). By \(B_G(A)\) we denote a sequence containing upper bounds on \(\alpha (G[A_i])\) for \(i \in \{1,2,\ldots ,k\}\). Let \(G=2K_3\). Then, for example, \(V(G)=\{1,2,\ldots ,6\}\), \(E(G)=\{\{1,2\},\{2,3\},\{3,1\},\{4,5\},\{5,6\},\{6,4\}\}\) andLet \(A'\) be a \(k'\)-tuple of subsets of V(G). A distribution \(D_G(A')\) is a \(k'\)-tuple of non-negative integers, and is our prediction about an arrangement of independent vertices of G in sets from \(A'\). Let \(G^{\boxtimes }=G_1 \boxtimes G_2 \boxtimes \ldots \boxtimes G_r\). Let \(i \in \{1,2,\ldots ,r\}\), \(S \subseteq V(G_i)\) and \(V_{G_i}(S) = V(G_1) \times V(G_2) \times \cdots \times V(G_{i-1}) \times S \times V(G_{i+1}) \times \cdots \times V(G_{r})\). From Hammack et al. (2011), for each clique Q of \(G_i\) we haveThus, if \(\mathcal {Q}=\{Q_1,Q_2,\ldots ,Q_k\}\) \((k \in \mathbb {N_+})\) is a set of cliques of \(G_i\) andthen we can choose \(B_{G^\boxtimes }((V_{G_i}(Q_1),V_{G_i}(Q_2),\ldots ,V_{G_i}(Q_k)))=(\alpha _i,\alpha _i,\ldots ,\alpha _i)\), where \(\alpha _i\) occurs k times. LetThe function \(\alpha ^*\) is multiplicative with respect to the strong product for all graphs (Scheinerman and Ullman 2011). Thus, from Observation 1 and (5) we getand finally \(\alpha _i\) holds the condition (6). Furthermore, from (7) and (3), for graphs without vertices with degree zero, also the following substitutionholds the condition (6).

Let \(i \in \{1,2,\ldots ,r\}\). Algorithm 6.3 (Distribution Distr), which takes as input a graph \(G=G_i\) and an upper bound \(\alpha _b=\alpha _i\), determines a distribution for a graph \(G^{\boxtimes }\). The algorithm Distr, whose running time is \(O(n^2)\), uses Algorithm 6.2 (Greedy Coloring GC), which has complexity \(O(n+m)\) (Kubale 2004). The algorithm GC takes as input a graph G and an arbitrary permutation P of the vertex set of G. GC in Distr legally colors the complement of G and hence produces a partition \(\mathcal {Q}\) of the vertex set of G into cliques (the so-called clique cover of G). Subsequently, Distr distributes \(\alpha _b=\alpha _i\) potential elements of an independent set roughly evenly (about \(\alpha _b/|Q|\) elements or less depending on the sum from line 19) among all vertices of Q (as well as among all subgraphs of \(G_1 \boxtimes G_2 \boxtimes \ldots \boxtimes G_{i-1} \boxtimes G_i[Q] \boxtimes G_{i+1} \boxtimes \ldots \boxtimes G_r\)) for all \(Q\in \mathcal {Q}\).

As we mentioned before, vertices chosen by Min strongly block an eventual choice of vertices in a further stage of the algorithm. Our greedy algorithm, i.e., Algorithm 6.4 (Greedy Algorithm Min-SP), significantly diminishes the mentioned effect by the use of generated distributions. The vertex set of \(G_1 \boxtimes G_2 \boxtimes \ldots \boxtimes G_r\) can be interpreted as the r-dimensional cuboid of the size \(|V(G_1)| \cdot |V(G_2)| \cdot \ldots \cdot |V(G_r)|\). Min-SP uses distributions in all r dimensions. Earlier Baumert et al. (1971), Jurkiewicz et al. (2015) and Codenotti et al. (2003), only one distribution was used at one time in algorithms for the maximum independent set problem in subclasses of the strong product of graphs to reduce a search space. The important point to note here is that in cases that are more interesting from an information theory point of view, i.e., if \(G_1=G_2=\cdots =G_r\), some parts of Min-SP are much simpler, e.g., we can determine one distribution and then we use it in all dimensions.

Min-SP defines four sets N, V, F and I, where N is the closed neighborhood of a chosen vertex \(\overline{v}^*\) (line 10), V is a set of vertices that are available for the next iterations, F is a set of forbidden vertices that are not available for the next iterations and I is an actual solution (an actual independent set). In lines 13–14 and lines 18–21, Min-SP updates distributions and degrees of all vertices from V, respectively. In line 17, elements of N and F are removed from V, but only degrees of vertices from N are updated.

An advantage of Min-SP is that we do not need to store edges of \(G^{\boxtimes }=G_1 \boxtimes G_2 \boxtimes \ldots \boxtimes G_r\) in a computer memory. This is important since \(|E(G^{\boxtimes })|\) almost always fast increases with r. In the memory, we only keep factors of \(G^{\boxtimes }\), and the adjacency relation \(\sim \) is directly checked from the conditions specified in the definition of the strong product (line 20).

Sometimes Min-SP produces I such that \(V(G^{\boxtimes })-N_{G^{\boxtimes }}[I]\ne \emptyset \), where \(N_{G}[I]=\bigcup _{v\in {}I} N_G[v]\) for \(I\in {}V(G)\) and a graph G. Thus, finally, it is possible to get a larger independent set of \(G^{\boxtimes }\), i.e., . We prefer such a method in our computations. It turns out that we also do not need to store edges of \(G^{\boxtimes }\) if we want to execute \({\textsc {Min}}(G^{\boxtimes }-N_{G^{\boxtimes }}[I])\). It can be done by a modification of Min similar to that we performed, when we constructed Min-SP.

In Table 3, we summarize results produced by Min-SP. The algorithm has a running time of \(O(|V|^{3})\).

We can approximate the Shannon capacity using (5) and the algorithm Min-SP. We show it by the following example.

In this section, we propose another modification of greedy algorithm Min, which is similar to Min-SP, but in addition, it uses distances between vertices of the strong product. We write down the new polynomial algorithm Min-SP2 (Algorithm 7.1) in a more compact form to make additional elements more visible. The modification, besides the advantages of Min-SP, has better accuracy (Table 4), but sometimes Min-SP gives a larger independent set than Min-SP2.

In contrast to Min-SP, Min-SP2 determines a set \(V^*\) of all vertices of V with the smallest degree (line 9). The set V is defined exactly the same as in Min-SP. In each iteration, Min-SP2 takes vertices from \(V^*\) with the largest \(\sum _{i=1}^r distr_{v_i}^{(i)}\) (i.e., it chooses vertices from ,,the least crowded region”, line 10). We also realized that independent vertices in a copy of a factor of a strong product are often placed far apart. Hence, in lines 11–16, Min-SP2 calculates \(D(\overline{v})\) for each \(\overline{v} \in V^*\) and selects one with the largest \(D(\overline{v})\), where \(D(\overline{v})\) measures the minimum distance from \(\overline{v}\) to the set of vertices of I that differ on exactly one coordinate with \(\overline{v}\). In contrast to Min, Min-SP2 gives the best results if we choose the first vertex \(\overline{v}\) with the smallest \(d(\overline{v})\). It is worth to note here that we always randomly relabel all input graphs at the beginning of our algorithm.

We observed an interesting phenomenon: When distributions used in Min-SP2 (lines 3–4) are not so precise (are relaxed), i.e., if numbers in distributions are too large (too optimistic), then this algorithm often produces optimal results. For example, let \(C_n\) be a cycle on n vertices, the following distribution (2, 2, 2, 2, 2, 2, 2) is too optimistic for \(C_7^{\boxtimes 2}\) since \(\alpha (C_7^{\boxtimes 2})=10<7\times 2=14\), but Min-SP2 for this strong product and distribution always gives a maximum independent set.

In our computational experiments, we got many optimal results produced by Min-SP2 with relaxed distributions and we did not find any counterexamples for \(|\textsc {Min}\hbox {-}\textsc {SP2}((C_{2k+1},C_{2k+1}))|=\alpha (C_{2k+1}\boxtimes C_{2k+1})\) with \(distr^{(1)}=distr^{(2)}=(\lceil k/2 \rceil ,\lceil k/2 \rceil ,\ldots ,\lceil k/2 \rceil \)), where \(\lceil k/2 \rceil \) occurs \((2k+1)\)–times and \(k\geqslant 2\).

According to the above considerations, we propose a relaxed version of the function Distr, which we call Relaxed Distribution RDistr (Algorithm 7.2).

Chalupa and Pospíchal (2014) investigated the growth of large independent sets in the Barabási–Albert model of scale-free complex networks. They formulated recurrent relations describing the cardinality of typical large independent sets and showed that this cardinality seems to scale linearly with network size. Independent sets in social networks represent groups of people, who do not know anybody else within the group. Hence, an independent set of a network plays a crucial role in community detection problems, since vertices of this set are naturally unlikely to belong to the same community (Chalupa and Pospíchal 2014; Whang et al. 2013). These facts imply that the number of communities in scale-free networks seems to be bounded from below by a linear function of network size (Chalupa and Pospíchal 2014).

Leskovec et al. (2010) introduced the Kronecker graph network model that naturally obeys common real network properties. In particular, the model assumes that graphs have loops and corresponds to the strong product (Hammack et al. 2011). Let \(i \geqslant 1\) and \(G'=G^{\boxtimes i}\). As mentioned earlier, the function \(\alpha \) is supermultiplicative and \(\alpha ^*\) is multiplicative with respect to the strong product for all graphs. Thus \((\alpha ^*(G))^{i}=\alpha ^*(G')\geqslant \alpha (G')\geqslant (\alpha (G))^i\) and hence \(|V(G')|^{c'} \geqslant \alpha (G') \geqslant |V(G')|^{c}\), where⁸\(c'=\log (\alpha ^*(G))/\log (V(G))\) and \(c=\log (\alpha (G))/\log (V(G))\). We have just showed that the cardinality of maximum independent sets, in the mentioned model, scale sublinearly with network⁹ size. Furthermore, if G is of type I, then \(\alpha (G') = |V(G')|^{c}\). These considerations show that the number of communities in scale-free networks seems to be bounded from below by a sublinear (rather than a linear) function of network size. It is worth pointing out that we can approximate (resp. predict) the number of communities, in the mentioned model (resp. real complex network), using Algorithms 6.4 or 7.1 (Greedy Algorithm Min-SP, Min-SP2).