{'fraction_non_alphanumeric': 0.03522003092122629, 'fraction_numerical': 0.005543195444775444, 'mean_word_length': 4.328511151295961, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Analyzing the Degree Distribution of the One-mode Projection of an Alphabetic Bipartite Network (\alpha-BIN)

The paper is being withdrawn since the authors felt that the submission is a little premature after a careful reading by some of the experts in this field.


1.
Introduction. Alphabetic Bipartite Networks (α-BiNs) are a special class of complex bipartite networks which was introduced by us in [12] and are appropriate for modeling discrete combinatorial systems (DCS) [13]. A DCS consists of a finite set of elementary units (e.g., codons and letters/phonemes) that serves as its basic building blocks and the system, in turn, is a collection of a potentially infinite number of discrete combinations of these units (e.g., genes and languages). A DCS can be easily represented as a bipartite network where one of the partitions corresponds to the elementary units and the other corresponds to the discrete combinations. There exists an edge between an elementary unit and a discrete combination iff the unit is a part of that discrete combination. The name α-BiN signifies the fact that the set of elementary units, in both human and genetic languages is referred to as an Alphabet.
There have been many studies pertaining to bipartite networks where both the partitions grow with time [2,7,11,14] and also some pertaining to non-growing bipartite networks [4,10]. However, those like α-BiNs in which one of the partitions remain fixed over time while the other grows have received much less attention. We identified this special class of networks in [3,12] and have proposed a growth model for them that is based on preferential attachment coupled with a tunable randomness component. We also presented exact analytical solution for the degree distribution of the alphabet nodes for certain sub-cases of the model at any instant of time. More specifically, we had dealt with the case of (a) sequential attachment where each node in the growing partition enters the system in a sequential manner with only one edge which gets preferentially attached to an alphabet node (e.g., an α-BiN consisting of speakers and the corresponding language they speak), (b) parallel attachment without replacement where a node in the growing partition enters with more than one edge and attaches itself with a set of distinct nodes in the fixed partition (e.g., an α-BiN of phonemes and phoneme inventories where an edge indicates that a particular phoneme is present in a particular inventory) and (c) parallel attachment with replacement where a node in the growing partition enters with more than one edge and is allowed to attach itself to a set of non-distinct nodes in the fixed partition (e.g., an α-BiN of codons and the genes formed from them where an edge denotes that a particular codon is a part of a gene).
From a bipartite network, such as the α-BiN, we can construct the network of shared discrete combinations, the so called one-mode projection onto the elementary units alone. Such an one-mode projection precisely represents a "collaboration network" that is usually defined as a network of actors (analogous to the elementary units) connected by a common collaboration act (analogous to being a part of the same discrete combination). The links in this network are representative of the intensity of collaboration between a pair of actors. In fact, there are a number of studies related to real-world bipartite networks and their corresponding one-mode projections [1,11,14]. For instance, it has been shown that for a movie-actor collaboration network, the degree distribution of the actor nodes in both the bipartite network and the one-mode projection follow a power-law [11,14]. Similarly, in case of scientific collaboration network, it has been observed that the degree distribution of the author nodes shows a fat-tailed behavior in both the bipartite network as well as the one-mode projection [14]. In case of board-director networks it has been found that the degree distribution of the director nodes in both the bipartite and the one-mode network can be roughly fitted using exponential functions [1,14].
Various models have been proposed and analytically solved to explain these observations [6,11,14]. However, as shown in [12], the degree distribution of the alphabet nodes in α-BiN asymptotically approaches a β-distribution rather than the widely observed power-law distribution.
In all the aforementioned studies on one-mode projection, a general trend has been to assume the sizes of the discrete combinations (i.e., the degree of the nodes in the growing partition) to be fixed to a constant. However, real-world systems (including DCSs) present us with examples where this size varies -neither all genes are composed of the same number of codons and nor all movies have the same cast size. Therefore, these sizes need to be viewed as random variables being sampled from a distribution rather than a constant -a fact that has not been taken into consideration in earlier analytical studies pertaining to bipartite networks. In this paper, our primary objective is to relax the general assumption outlined above and, thereby, present a detailed and in-depth analysis of the one-mode projection of α-BiN onto the alphabet nodes.
In some of the previous studies, the main focus has been on the degree distribution of the alphabet nodes of real-world α-BiNs like the phoneme-language network (phonemes/speech sounds are the basic units and the sound systems of languages are the discrete combinations) while the properties of the degree distribution of the one-mode projection of such a network remains largely unexplained. For instance, in [3] the degree distribution of the network of co-occurrence of phonemes (i.e., two phonemes are connected by an edge as many times as they co-occur across the sound systems of different languages) which is the one-mode projection of the phoneme-language network, differs significantly from the theoretical predictions. In this paper, we identify the gap in the analysis and suitably extend the theoretical framework to explain quite accurately the emergent degree distribution of the onemode projection of α-BiNs. We relax the general assumption that the sizes of the discrete combinations are fixed and view them as random variables being sampled from a particular distribution. Our analytical results show that this distribution indeed affects the degree distribution of the one-mode projection even though it does not affect the degree distribution of α-BiN. In fact, these results are in good agreement with those obtained from the stochastic simulations. We further analyze four real-world α-BiNs, two of which are taken from the domain of natural language while the other two are from the domains of biology and society respectively. We observe that the empirical results obtained from the analysis of these α-BiNs agree with our finding.
An equally important contribution of this work is that the theoretical framework developed can not only be applied to analyze the degree distribution of the one-mode projection of α-BiNs but also can be easily used for the analysis of the one-mode projection of any bipartite network in general for which the degree distribution of the two partitions are known.
The rest of the paper is organized as follows. Section 2 presents a review of our work related to α-BiNs. In section 3, we analyze the degree distribution of the one-mode projection of α-BiN. In section 4, we corroborate our finding through the empirical analysis of four real-world α-BiNs. Finally, we conclude by enumerating our major contributions and pointing to some important implications of the current work.

2.
A brief review of the model and the associated predictions. A bipartite graph G is a 3-tuple U, V, E , where U and V are mutually exclusive sets of nodes (also known as the two partitions) and E ⊆ U × V is the set of edges that run between these partitions. Let us denote the elementary units of a DCS by the nodes in the partition U and let each unique discrete combination of the elementary units be denoted as a node in the partition V. There exists an edge between a basic unit u ∈ U and a discrete combination v ∈ V iff u is a part of v.
The growth of this network has been described in [3,12] through a simple model based on preferential attachment coupled with a tunable randomness component. Suppose that the partition U has N nodes labeled as u 1 to u N . At each time step, a new node is introduced in the set V which connects to µ nodes in U based on a predefined attachment rule. Let v t be the node added to V during the t th time step. Let A(k t i ) denote the probability that a new node v t entering V attaches itself to a node u i ∈ U , where k t i refers to the degree of the node u i at time step t. A(k t i ) defines the attachment kernel and takes the form where γ is the tunable parameter that controls the amount of randomness in the system. The lower the value of γ the higher is the randomness. Using techniques of linear algebra we can derive an approximate closed form solution for p k,t that approaches a β-distribution asymptotically with time and can be expressed as where η = N/µγ and A is a normalization constant. Formally, for an α-BiN U, V, E the one-mode projection onto the nodes U is a graph If there are w such nodes in V which are connected to both u i and u j in G, then there are w edges linking u i and u j in the one-mode projection G U . Alternatively, one can think of G U as a weighted graph, where the weight of the edge (u i , u j ) is w.
One can easily calculate the degree of the nodes in the one-mode projection G U if each node introduced in V connects to exactly µ nodes in U . In other words, the size of each discrete combination in this case is assumed to be equal to a constant µ. Consider a node u ∈ U that has degree k in the bipartite network. Therefore, u is connected to k nodes in V and each of these k nodes are in turn connected to µ − 1 other nodes in U. Defining the degree of a node as the number of edges attached to it, in the one-mode projection, u has a degree of q = k(µ − 1). However, it is not realistic to assume that the size of each discrete combination i.e., the degree of each node in V is a constant µ. Real-world DCSs present us with instances where this size varies and therefore, it has to be thought of as a random variable that is being sampled from a distribution. Indeed, as we shall see, this distribution affects the degree distribution of the alphabet nodes in the one-mode projection even though their degree distribution in the α-BiN remains unaffected. The reason for this is that the degree q of u in the one-mode projection is dependent on this size while the degree k in α-BiN is not as long as the mean size of the discrete combinations is equal to µ. Note that in this case once again the denominator of eq. (1) is equal to µγt + N as in our earlier model (i.e., where the size is a constant µ). Hence, the probability of attachment is largely the same and k remains unchanged.
3. Analysis of the degree distribution of the one-mode projection of α-BiN. Let us assume that the sizes of the discrete combinations are sampled from a distribution f d and then q becomes sensitive to this distribution although k does not. Let us call the probability that the node u having degree k in α-BiN ends up as a node having degree q in the one-mode projection F k (q). Further, let us denote the degree distribution of the alphabet nodes in the one-mode projection by p u (q). If we assume that the degrees of the k nodes in V to which u is connected to are The probability that the node u in α-BiN is connected to a node in V of degree: One might apply the generating function (GF) formalism introduced in [8] to calculate the degree distribution of the alphabet nodes in the one-mode projection as follows. Let f (x) denote the GF for the distribution of the sizes of the discrete combinations. In other words, The authors in [8] (see eq. (70)) have shown that g(x) can be correctly expressed as If f d and p k are distributions for which a closed form is known for f (x) and p(x) then it is easy to derive a closed form solution for g(x) (e.g., if both f d and p k are Poisson-distributed). However, in our case, p k is β-distributed as shown in eq. (2) and there is no known closed form expression for p(x). Therefore, it is difficult to carry out our analysis any further using the GF formalism. Note that, in general, there can be many instances of bipartite networks (in addition to α-BiNs) where the closed form expression for the GFs of the distributions f d and p k are unknown.
An alternative way to approach the problem would be to calculate a generic expression for p u (q) from the first principles. We shall therefore attempt to obtain such an expression, propose a suitable approximation for it and then check for its dependence on the choice of f d . As we shall see, in many cases it is even possible to obtain closed form solution for the expression of p u (q). The appropriately normalized probability that the node u in α-BiN is connected to nodes of degree d 1 , (each such connection is independent of the others). Under the constraints d 1 + d 2 + · · · + d k = q, we have We can now add up these probabilities for all values of k weighted by the probability of finding a node of degree k in α-BiN. Thus we have, or, For the rest of the analysis, we shall assume that d 1 d 2 . . . d k is approximately equal to µ k . In other words, we assume that the arithmetic mean of the distribution is close to the geometric mean, which holds when the variance of the distribution is low. We shall shortly discuss in further details the bounds of this approximation. However, prior to that, let us investigate, how this approximation helps in advancing our analysis. Under the assumption d1d2...d k µ k = 1, F k (q) can be thought of as the distribution of the sum of k random variables each sampled from f d . In other words, F k (q) tells us how the sum of the k random variables is distributed if each of these individual random variables are drawn from the distribution f d . This distribution of the sum can be obtained by the iterative convolution of f d for k times 1 (see [5] for details). If the closed form expression for the convolution exists for a distribution, then we can obtain an analytical expression for p u (q). In the following, we shall attempt to find an expression for p u (q) assuming four different forms of the distribution f d . As we shall see, F k (q) is different for each of these forms, thereby, making the degree distribution of the nodes in G U sensitive to the choice of f d . Since in the expression for q (eq. (3)) we need to subtract one from each of the d i terms therefore the distribution F k (q) has to be shifted accordingly. We shall denote this approximate and shifted version of F k (q) byF k (q).

3.1.
Effect of the sampling distribution f d . In this section, we shall analytically study the effect of the sampling distribution f d on the degree distribution of the one-mode projection of α-BiN. Note that while we use continuous functions for the theoretical analysis the simulations are carried on with their discrete counterparts. In other words, we use the probability mass functions rather than the probability density functions for our simulations. Delta function: Let f d be a delta function of the form Note that this boils down to the case where the size of each discrete combination is a constant µ and therefore, d1d2...d k µ k is exactly equal to 1. If this delta function is convoluted k times then the sum should be distributed as Therefore, p u (q) exists only when q = k(µ − 1) or k = q/(µ − 1) and we have (this result has also been obtained through a different approach in [3]) Normal distribution: If f d is a normal distribution of the form N (µ, σ 2 ) then the sum of k random variables sampled from f d is again distributed as a normal distribution of the form N (kµ, kσ 2 ). Therefore,F k (q) is given bẙ If we substitute the density function for N we have Hence, p u (q) is given by Exponential distribution: If f d is an exponential distribution of the form E(λ) where λ = 1/µ then the sum of the k random variables sampled from f d is known to take the form of a gamma distribution Γ(q; k, µ). Therefore, we have Substituting the density function we have where λ ′ = 1/(µ − 1). Hence, p u (q) is given by Power-law distribution: There is no known exact solution for the sum of k random variables each of which is sampled from f d that is power-law distributed with exponent λ i . However, as noted in [15,16], asymptotically the tail of the distribution obtained from the convolution 2 is dominated by the smallest exponent that is minimum(λ 1 , λ 2 , . . . , λ k ). Note that due to this approximation the resultant degree distribution should indicate a better match with the stochastic simulations towards the tail. We haveF k (q) ∼ kq −minimum(λ1,λ2,...,λ k ) (17) However, since we are sampling from the same distribution each time so λ 1 = λ 2 = · · · = λ k = λ andF k (q) ∼ kq −λ (18) Consequently, p u (q) can be expressed as Figure 1(a) shows the cumulative degree distribution (i.e., the probability P x that a node has degree ≥ x) of the alphabet nodes in α-BiN assuming that the degrees of the nodes in V are sampled from (i) normal, (ii) delta, (iii) exponential and (iv) power-law distributions each having the same mean (µ = 22). Note that the standard deviation (σ) of the normal distribution is controlled in such a way that the value of the random variable d is never negative. The results are obtained by averaging 100 stochastic simulations of the model. Since k is not affected by the choice of this distribution therefore, P k remains same as long as the means of these distributions are same. Figure 1(b) shows the degree distributions of the one-mode projections corresponding to the α-BiNs generated for Figure 1(a). The result clearly implies that the degree distribution of the one-mode projection varies depending on how the degrees of the nodes in V are distributed although the degree distribution remains unaffected for all the α-BiNs generated. Figure 1(c)-(f) shows the match of the analytical expressions (with appropriate normalization) derived for normal (eq. (13)), delta (eq. (10)), exponential (eq. (16)) and power-law (eq. (19))  23); the green dots indicating the case where the sizes of the discrete combinations are fixed to a constant µ = 22 are again provided as a reference to demonstrate that it is much worse than even with the respective stochastic simulations. The figures show that the analytically obtained expressions are in good agreement with the simulations. Note that in case of power-law, while the heavy tail matches perfectly, the low degree zone deviates slightly which is a direct consequence of the approximation used in the convolution theory for power-law.
Finally, it remains to be mentioned that in many cases it is possible to derive a closed form expression for p u (q). One can think of p kFk (q) as a function F in q and k, i.e., p kFk (q) = F (q, k). If F (q, k) can be exactly (or approximately) factored into a form like F (q) F (k) then p u (q) becomes Changing the sum in eq. (20) to its continuous form we have where A is a constant. In other words, the nature of the resulting distribution is dominated by the function F (q). For instance, in case of exponentially distributed f d , with some algebraic manipulations and certain approximations one can show that (see the yellow dots in Figure 1(e)) Similarly, in case of power-law one can show that (see the yellow dots in Figure 1(f)) Therefore, it turns out that when this factorization is possible, the resulting degree distribution of the one-mode projection is largely dominated by that part of the convolution which is only dependent on q.
3.2. Approximation Bounds. We shall employ the GF formalism to find the necessary condition (in the asymptotic limits) for our approximation to hold. More precisely, we shall attempt to estimate the difference in the means (or the first moments) of the exact and the approximate expressions for p u (q) and discuss when this difference is negligible which in turn serves as a necessary condition for the approximation to be valid. We shall denote the generating function for the approximate expression of p u (q) as g app (x). In this case, the GF encoding the probability that the alphabet node u is connected to a node in V of degree d is simply f (x)/x and consequently,F k (q) is given by (f (x)/x) k . Therefore, Now we can calculate the first moments for the approximate and the exact p u (q) by evaluating the derivatives of g app (x) and g(x) respectively at x = 1. We have Similarly, Thus, the mean of the approximate p u (q) is smaller than the actual mean by (t/N )σ 2 . Clearly, for σ = 0, the approximation gives us the exact solution, which is indeed the case for delta functions. Also, in the asymptotic limits, if σ 2 ≪ N (with a scaling of 1/t), the approximation holds good. However, as the value of σ increases the results start deteriorating (see the brown dots in Figure 1(c)).

4.
Experiments with real-world α-BiNs. In this section, we shall present case studies of four different real-world α-BiNs to corroborate our findings in the earlier section. While the first two are instances from natural language, the third and the fourth are instances from biology and society respectively. In each case, the results obtained assuming the actual distribution of the size of the discrete combinations outperform those obtained assuming the size to be a constant (always equal to the average size of the discrete combinations). For all the stochastic simulations of the model, γ best indicates the value of the parameter γ where the degree distribution of the alphabet nodes in the bipartite network generated indicates the best match with the corresponding real bipartite network (i.e, when the mean difference in the values of P k for similar k is least between the two degree distributions). The four networks and the associated results are as follows.
Phoneme-phoneme Network (PhoNet). PlaNet or the Phoneme-language Network is an α-BiN where the two partitions respectively stand for the consonants (fixed alphabet) and the language inventories (growing discrete combinations) where an individual inventory is defined as a repertoire of distinct consonants used by the speakers of that language for communication. PhoNet is the corresponding one-mode projection of PlaNet onto the consonant nodes (see Table 1 for details). Figure 2 clearly shows that the degree distribution obtained from the stochastic simulations (for γ best ) of the model assuming the actual distribution of the consonant inventory sizes (blue symbols) matches significantly better with that of the empirical PhoNet (red symbols) than the case where the sizes are assumed to be equal to a constant (green symbols).
Vowel-vowel Network (VoNet). VlaNet or Vowel-language Network is similar to PlaNet with the exception that the two partitions here respectively stand for the universal set of vowels (fixed alphabet) and the language inventories (growing discrete combinations) 3 . VoNet (like PhoNet) is the one-mode projection of VlaNet onto the vowel nodes (see Table 1 for details). Once again we observe (see Figure 2) that the degree distribution of the empirical VoNet (red symbols) indicates a closer match with the case where the stochastic simulation (for γ best ) assumes the actual vowel inventory size distribution (blue symbols) than the case where its assumes the size to be a constant (green symbols). Protein-protein Network (ProtNet). ProComp or Protein-Complex Network is an α-BiN where the nodes in U correspond to distinct proteins and those in V correspond to unique protein complexes. ProtNet is the corresponding one-mode projection of ProComp onto the protein nodes (see Table 1 for details). The degree distribution (see Figure 2) of empirical ProtNet (red symbols) matches significantly well with the simulation results (for γ best ) if the actual complex size distribution is taken into account (blue symbols) compared to the case where this size is assumed to be a constant (green symbols).
Station-station Network (StaNet). StaTNet or the Station-Train network is an α-BiN in which the nodes in the partition U represents the stations 4 while those in V represents the trains and there is an edge in this network iff a train in its route halts at a station. StaNet is the one-mode projection of StaTNet onto the station nodes (see Table 1 for details). Once again, the degree distribution (see Figure 2) of empirical StaNet (red symbols) shows a closer match with the case where the stochastic simulations (for γ best ) are performed assuming the distribution of train frequency (blue symbols) than the case where this frequency is assumed to be equal to the average frequency and hence a constant (green symbols).

5.
Conclusion. In this paper, we have analyzed the degree distribution of the one-mode projection of an α-BiN used for modeling discrete combinatorial systems. More specifically, we identified that the degree distribution of this network varies if the sizes of the discrete combinations are assumed to be random variables rather than a constant. Further, we derived approximate analytical expressions (and closed form solutions in certain cases) for the degree distributions assuming different distributions from where these sizes are sampled. The analytical results are in good agreement with the stochastic simulations. We also discussed about the bounds of the approximation used for deriving the analytical expression for the degree distribution. Finally, we presented four case studies to further support our finding.
It is worthwhile to mention here that the theoretical framework that we developed for analyzing the degree distribution of the one-mode projection of an α-BiN can be applied to any other type of bipartite network in general. For instance, in case of the model proposed in [14] for movie-actor networks, the distribution of the cast size in the bipartite network is assumed to be a constant while the degree distribution p k of the actor nodes is found to follow a power-law. Therefore, it is easy to see that this particular case shall follow an analysis very similar to that outlined in eqs. (8), (9) and (10).