Markus Holzer

Martin Kutrib

One-Time Nondeterministic Computations

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The concept of nondeterministic machines was introduced in the seminal paper of Rabin and Scott [START_REF] Rabin | Finite automata and their decision problems[END_REF] on finite automata and their decision problems from 1959. Hopcroft [START_REF] Hopcroft | Automata theory: Its past and future[END_REF] writes in his survey "Automata Theory: Its Past and Future" about the nondeterministic finite automaton (NFA) model in the above mentioned paper:

"It was shown that this model was equivalent to the deterministic one. The fact that two models which were so different gave rise to the same sets, along with the fact that both were equivalent to the regular expression notation, indicated that these models were fundamental. This paper was very influential in shaping automata theory . . . "

Nondeterminism turned out to be a very fruitful concept in different areas of computer science like, for example, computability theory, complexity theory, automata theory, formal language theory, etc., to mention only a few. Two of the most prominent problems related to nondeterminism are the P versus NP problem (see, for example, [START_REF] Hartmanis | Gödel, von Neumann and the P =?NP problem[END_REF]) and the LBA problem (see, for example [START_REF] Hartmanis | The LBA problem and its importance in the theory of computing[END_REF]). The former problem is listed as one of the ten Millennium Problems from the Clay Mathematics Institute, Cambridge, Massachusetts, USA, which is the sole computer science problem in that list.

Although NFAs are as powerful as deterministic one, as already mentioned above, the former model can offer exponential saving in space compared with deterministic finite automata (DFAs), that is, given some n-state NFA one can always construct a language equivalent DFA with at most 2 n states [START_REF] Rabin | Finite automata and their decision problems[END_REF]. This so-called powerset construction turned out to be optimal, in general. That is, the bound on the number of states is tight in the sense that for an arbitrary n there is always some n-state NFA which cannot be simulated by any DFA with less than 2 n states [START_REF] Meyer | Economy of description by automata, grammars, and formal systems[END_REF][START_REF] Moore | On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata[END_REF]. It is worth mentioning that Moore's NFA contains a sole nondeterministic state, while Meyer and Fischer's nondeterministic automaton has n -1 nondeterministic states. In both NFAs the nondeterministic branching, that is, the maximal number of transitions with the same label leaving a state, is bounded by two, thus by a constant. This can be seen as a first indication that not all NFAs make equal use of nondeterminism. In fact, nondeterminism is a resource and its usage can be accurately quantified. There are several possibilities to do so. For instance, one is to count the number of nondeterministic moves during the computation, while another one depends on the number of the successor states and is called branching and guessing. Results on these quantifications are subsumed under the name limited nondeterminism in the literature, see, for example, [START_REF] Goldstine | Descriptional complexity of machines with limited resources[END_REF] for a survey.

Here we give a new interpretation of nondeterminism. On the one hand, we are still interested in the power of nondeterminism with respect to computations and conciseness, but on the other hand, its usage should be heavily restricted. The restriction we are introducing is that of one-time nondeterminism, which means that at the outset the automaton is nondeterministic, but whenever it performs a guess, this guess is fixed for the rest of the computation. This is a clear change on the semantics of nondeterminism. We will study this new concept for finite automata and pushdown machines. Although one-time nondeterminism does not increase the accepting power of ordinary finite state devices, their conciseness is even greater than that of ordinary nondeterministic finite automata compared to deterministic ones. In general, an n-state one time nondeterministic finite automaton (OTNFA) can be simulated by an (n+1) n k•n -state deterministic finite automaton, where k is the size of the input alphabet. In general this bound is over-counted. A slightly better estimate is obtained by using the notion of the degree of nondeterminism d for finite state devices, which is defined as the product of all non-zero size successor sets of a state. Formally

d(M ) = (q,a)∈Q×Σ |δ(q,a)| =0
|δ(q, a)|, where Q is the set of states, Σ the input alphabet, and δ the nondeterministic transition function of M . A better upper bound on the above mentioned simulation of an OTNFA M is then (n + 1) d(M ) . This bound is tight in a special case, because we can give an example of an n-state OTNFA M of nondeterministic degree d(M ) = n such that (n + 1) n states are sufficient and necessary in the worst case for an equivalent deterministic finite automaton. For pushdown automata the results on the descriptional complexity are even more dramatic. First of all it is shown that one-time nondeterministic pushdown automata (OTNPDA) accept exactly the union closure of the deterministic context-free languages. This is a well-known language family which properly lies between the deterministic context-free languages and the context free ones. We utilize this characterization and show that the trade-offs between OTNPDAs and deterministic ones, as well as between ordinary nondeterministic pushdown automata and OTNPDAs are non-recursive. That is, the bound between two equivalent machines of different types cannot be bounded by any recursive function. This is quite exceptional because the use of nondeterminism is highly restricted to the bare necessities.

Preliminaries

Let Σ * denote the set of all words over the finite alphabet Σ. The empty word is denoted by λ, and Σ + = Σ * \ {λ}. The reversal of a word w is denoted by w R . For the length of w we write |w|. For the number of occurrences of a symbol a in w we use the notation |w| a . Set inclusion is denoted by ⊆ and strict set inclusion by ⊂. We write 2 S for the power set and |S| for the cardinality of a set S.

We recall some notation for descriptional complexity. Following [START_REF] Holzer | Descriptional complexity -An introductory survey[END_REF] we say that a descriptional system S is a set of finite descriptors such that each D ∈ S describes a formal language L(D), and the alphabet alph(D) over which D represents a language can be deduced from D. The family of languages represented (or described ) by S is L (S) = { L(D) | D ∈ S }. For every language L, the set S(L) = { D ∈ S | L(D) = L } is the set of its descriptors in S. A complexity measure for a descriptional system S is a total recursive mapping c : S → N.

Finite automata or (deterministic) pushdown automata can be encoded over some fixed alphabet such that their input alphabets can be extracted from the encodings. The sets of these encodings are descriptional systems S 1 and S 2 , and L (S 1 ) is the family of regular languages and L (S 2 ) is the family of (deterministic) context-free languages. Examples for complexity measures for finite automata or pushdown automata are the total number of symbols, that is, the length of the encoding (length), or, in the former case, the number of states and, in the latter case, the product of the number of transition rules and the maximal number of symbols pushed in one step.

Here we only use complexity measures that are recursively related to length. If there is a total recursive function g : N × N → N such that, for all D ∈ S, length(D) ≤ g(c(D), |alph(D)|), then c is said to be an s-measure. If, in addition, for any alphabet Σ, the set of descriptors in S describing languages over Σ is recursively enumerable in order of increasing size, then c is said to be an snmeasure. Clearly, the number of states is an sn-measure for finite automata.

Whenever we consider the relative succinctness of two descriptional systems S 1 and S 2 , we assume that the intersection L (S 1 ) ∩ L (S 2 ) is non-empty. Let S 1 and S 2 be descriptional systems with complexity measures c 1 and c 2 , respectively. A total function f : N → N is an upper bound for the increase in complexity when changing from a descriptor in S 1 to an equivalent descriptor in S 2 , if for all

D 1 ∈ S 1 with L(D 1 ) ∈ L (S 2 ), there exists a D 2 ∈ S 2 (L(D 1 )) such that c 2 (D 2 ) ≤ f (c 1 (D 1 )
). If there is no recursive upper bound, then the trade-off for changing from a description in S 1 to an equivalent description in S 2 is said to be non-recursive. Non-recursive trade-offs are independent of particular sn-measures.

One-Time Nondeterministic Finite Automata

We investigate one-time nondeterministic finite automata. The basic idea is that at the outset the automaton is nondeterministic. But whenever it performs a guess, this guess is fixed for the rest of the computation.

A nondeterministic finite automaton (NFA) is a system M = Q, Σ, δ, q 0 , F , where Q is the finite set of internal states, Σ is the finite set of input symbols, q 0 ∈ Q is the initial state, F ⊆ Q is the set of accepting states, and δ : Q × Σ → 2 Q is the transition function. A configuration of a finite automaton M is a tuple (q, w), where q ∈ Q and w ∈ Σ * . If a is in Σ and w in Σ * , then we write (q, aw) M (p, w) if p is in δ(q, a). As usual, the reflexive transitive closure of M is denoted by * M . The subscript M will be dropped from M and * M if the meaning is clear. Then the language accepted by M is defined as

L(M ) = { w ∈ Σ * | (q 0 , w) * M (p, λ) for some p ∈ F }.
A state q is nondeterministic on a letter a in M , if |δ(q, a)| ≥ 2, and state q is nondeterministic in M , if it is nondeterministic on some letter a ∈ Σ. Moreover, a state q is reachable in M if there is an input word w with (q 0 , w) * M (q, λ). Without loss of generality we assume that any state of a (non)deterministic finite automaton is reachable.

A finite automaton M is partial deterministic (partial DFA) if and only if |δ(q, a)| ≤ 1, for all q ∈ Q and a ∈ Σ, and the device M is deterministic (DFA) if and only if |δ(q, a)| = 1, for every q ∈ Q and a ∈ Σ. In these cases we simply write δ(q, a) = q for δ(q, a) = {q } assuming that the transition function is a (partial) mapping δ : Q × Σ → Q. Observe, that every partial DFA can be made complete by introducing a non-accepting sink state. So, any DFA is complete, that is, the transition function is total, whereas for partial DFAs and NFAs it is possible that δ maps to the empty set.

Next, the idea of one-time nondeterministic finite automata is formalized as follows: let M = Q, Σ, δ, q 0 , F be an NFA and

(q 0 , w) = (q 0 , a 0 w 0 ) M (q 1 , w 0 ) = (q 1 , a 1 w 1 ) M • • • M (q n , w n-1 ) = (q n , a n w n ) M (q n+1 , w n ) = (q n+1 , λ),
be a computation of M on input w = a 0 w 0 ∈ Σ + . A computation is permissible if and only if (q i , a i ) = (q j , a j ) implies q i+1 = q j+1 , for all 0 ≤ i < j ≤ n, or the computation is trivial, that is, it consists of (q 0 , λ) only. Now, M is said to be one-time nondeterministic if and only if it may only perform permissible computations. In this case we call M a one-time nondeterministic finite automaton (OTNFA). A word w is permissible acceptable by M if there is a permissible computation that ends in an accepting state of M . The language accepted by an OTNFA M is

L p (M ) = { w ∈ Σ * | word w is permissible acceptable by M }.
In order to illustrate the definitions we continue with an example.

Example 1. Consider the NFA M with a single nondeterministic state depicted on the left of Figure 1. It is easy to see that M accepts all words where the next to last letter is an a, that is, the language (a + b) * a(a + b). When interpreting M as an OTNFA, then only permissible computations are allowed. This means, that for the sole nondeterministic state either the a-self-loop from state 1 to itself or the a-transition leading form state 1 to 2 can be used during the computation, but not both. Thus, we can think of doing a computation either in the finite automaton M or M shown in the middle of or on the right of Figure 1. Therefore, the language accepted by the OTNFA M is equal to b * a(a + b), because the automaton in the middle does not accept anything.

The following statement is trivial since the permissible computations of an NFA are a subset of all possible computations. The strictness of the inclusion follows by the above given example. Lemma 2. Let M be a nondeterministic finite automaton. Then the inclusion L p (M ) ⊆ L(M ) holds, and there is a device M such that it is proper.

Before we consider the computational power of OTNFAs in more detail, we need some further notation. Let M = Q, Σ, δ, q 0 , F be an NFA. An automaton M = Q , Σ , δ , q 0 , F is compatible with M if and only if (i) Q = Q, (ii) Σ = Σ, (iii) q 0 = q 0 , (iv) F = F , and (v) δ (q, a) ⊆ δ(q, a), for every q ∈ Q and a ∈ Σ. If M is compatible with M , then we write M ≺ M . We further define that M is non-empty compatible with M , if and only if M is compatible with M and δ(q, a) = ∅ implies δ (q, a) = ∅, for every q ∈ Q and a ∈ Σ. If M is non-empty compatible with M , then we write M ≺ ne M . Note that every automaton is (non-empty) compatible with itself. Obviously, M ≺ ne M implies M ≺ M , but the converse implication does not hold in general. Both automata M and M depicted in Figure 1 are non-empty compatible with M shown in the same figure on the left; for short M ≺ ne M and M ≺ ne M . Now we are ready for the next theorem.

Theorem 3. Let M be an OTNFA. Then L p (M ) = M ∈Dne(M ) L(M ), where D ne (M ) = { M | M is a partial DFA with M ≺ ne M }.
Proof. The inclusion from left to right is seen as follows: let M = Q, Σ, δ, q 0 , F . Consider any word w ∈ L p (M ). Since w belongs to the language in question, there is a permissible computation of the form (q 0 , λ), if w = λ or (q 0 , w) = (q 0 , a 0 w 0 ) M (q 1 , w 0 ) = (q 1 , a

1 w 1 ) M • • • M (q n , w n-1 ) = (q n , a n w n ) M (q n+1 , w n ) = (q n+1 , λ)
with q n+1 ∈ F , suitable a 0 , a 1 , . . . , a n in Σ, and words w 0 , w 1 , . . . , w n in Σ * . It is not hard to see that there is a partial DFA M = Q, Σ, δ , q 0 , F ) with M ≺ ne M satisfying δ (q i , a i ) = q i+1 , for 0 ≤ i ≤ n-the non-used transitions during the considered computation are appropriately induced by the OTNFA M . Therefore, the word w is accepted by the partial DFA M , that is, w ∈ L(M ). Thus, w belongs to M ∈Dne(M ) L(M ), since M ∈ D ne (M ). This shows that L p (M ) ⊆ M ∈Dne(M ) L(M ).

For the converse inclusion we argue as follows: let M be any partial DFA from D ne (M ). Consider a word w ∈ L(M ). As above, there is a computation of the form (q 0 , λ), if w = λ or (q 0 , w) = (q 0 , a 0 w 0 ) M (q 1 , w 0 ) = (q 1 , a

1 w 1 ) M • • • M (q n , w n-1 ) = (q n , a n w n ) M (q n+1 , w n ) = (q n+1 , λ)
with q n+1 ∈ F , suitable letters a 0 , a 1 , . . . , a n in Σ, and words w 0 , w 1 , . . . , w n in Σ * . Since this is a deterministic computation one can interpret it as a permissible computation of M , since M can simulate every step of the partial DFA M . Therefore we conclude that w ∈ L p (M ), hence L p (M ) ⊇ L(M ). Note that the given argumentation holds for every M ∈ D ne (M ) and therefore L p (M ) ⊇ M ∈Dne(M ) L(M ). This proves the stated claim.

Theorem 3 shows that OTNFAs accept only regular languages, because they are closed under finite union. Although OTNFAs do not improve the computational power of ordinary finite automata, the question on the descriptional complexity of these devices arises. The statement of Theorem 3 give us some hint, that the relative succinctness compared to ordinary finite state devices may be enormous, since the union on the right-hand side of L p (M ) = M ∈Dne(M ) L(M ) runs over a large number of different M from D ne (M ). In fact, our intuition is supported by the next result, which states a very large upper bound. Theorem 4. Let M be an n-state OTNFA with a k-letter input alphabet. Then (n + 1) n k•n states are sufficient for a DFA to accept the language L p (M ).

Proof. Let M = Q, Σ, δ, q 0 , F . Then L p (M ) = M ∈Dne(M ) L(M ) by Theorem 3, where D ne (M ) = { M | M is a partial DFA with M ≺ ne M }. In order to accept the union on the right-hand side by a DFA, we apply the standard cross-product construction [START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF]. To this end, we complete the involved partial automata from D ne (M ), which results in ordinary DFAs with at most n + 1 states. Then the upper bound on the number of states for any DFA accepting L p (M ) is (n + 1) |Dne(M )| . Thus, it remains to obtain an upper bound on the size of D ne (M ).

An automaton M in D ne (M ) is constructed from M by cycling trough all states q and letters a and distinguishing the following cases: (i) if δ(q, a) = ∅, then δ (q, a) = ∅, (ii) if δ(q, a) = {p}, then δ (q, a) = {p}, and (iii) if δ(q, a) = {p 1 , p 2 , . . . , p k }, for k ≥ 2, then δ (q, a) = {p i }, for some i with 1 ≤ i ≤ k. Since |δ(q, a)| ≤ n, for every state q and letter a, we conclude that the size of D ne (M ) is bounded from above by n k•n . Hence we get the stated upper bound of (n+1) n k•n states for a DFA accepting the language L p (M ).

It turns out that the upper bound on the number of states of a DFA accepting L p (M ), for a OTNFA M , is more accurate the better we can determine the size of D ne (M ). A greater precision is obtained by defining the nondeterministic degree d(M ) of an OTNFA M with state set Q and input alphabet Σ as d(M ) = (q,a)∈Q×Σ |δ(q,a)| =0 |δ(q, a)|. Then it is easy to see that the following lemma holds. Hence we can reformulate the upper bound given in Theorem 4 as follows: Corollary 6. Let M be an OTNFA with nondeterministic degree d(M ). Then any DFA that accepts the language L p (M ) needs at most (n + 1) d(n) states.

In the remainder of this section we obtain that the bound stated in the previous corollary can be reached already for a OTNFA with a sole nondeterministic state, that is nondeterministic for only one input symbol.

Theorem 7. There is a n-state OTNFA M with a sole nondeterministic state, that is nondeterministic only for one input symbol, and has nondeterministic degree n, such that (n + 1) n states are sufficient and necessary in the worst case for a DFA to accept the language L p (M ).

Proof. The upper bound of (n + 1) d(n) states for a DFA accepting the language L p (M ) follows from Corollary 6. For the lower bound we argue as follows: consider the OTNFA whose transition function δ on the letters a, b, c, and d is depicted in Figure 2.

By the ≺ ne -relation the OTNFA M gives rise to several partial DFAs M j , for 1 ≤ j ≤ n, where M j = {1, 2, . . . , n}, {a, b, c, d}, δ j , 1, {n} and the transition function δ j is equal to δ on the letters a, b, and c, and for the letter d we have andδ j (i, d) is undefined otherwise. These partial DFAs M 1 , M 2 , . . . , M n are the basic building blocks in the cross-product construction for the (ordinary) DFA M accepting the language L p (M ). Define the DFA M = Q , {a, b, c, d}, δ , q 0 , F , where the set of states is equal to Q = ({1, 2, . . . , n}∪{-}) n , the initial state is q 0 = (1, 1, . . . , 1), and

δ j (i, d) = {j}, if i = 1, δ j (i, d) = {i}, if 2 ≤ i < n,
F = { f ∈ Q | f [i] = n, for some 1 ≤ i ≤ n }, where f [i] refers to the ith component of f ∈ ({1, 2, . . . , n} ∪ {-}) n . The transition function is given by δ (f, a) = (δ 1 (f [1], a), δ 2 (f [2], a), . . . , δ n (f [n], a)), for every f ∈ Q and a ∈ Σ.
Here we assume that whenever some δ i (f [i], a) is undefined, then the component is set to -. In order to prove our statement we need to show that the DFA M is minimal. The proof that every state in M is reachable and defines a distinct equivalence class utilizes some results from semigroup theory since one can identify the states of M with partial mappings from [n] to [n].

One-Time Nondeterministic Pushdown Automata

Now we turn to generalize the definitions of OTNFAs to pushdown automata. Nondeterministic pushdown automata are well known for capturing the contextfree languages.

Let Σ be an alphabet. For convenience, we use Σ λ for Σ ∪ {λ}. A nondeterministic pushdown automaton (NPDA) is a system M = Q, Σ, Γ, δ, q 0 , ⊥, F , where Q is a finite set of internal states, Σ is the finite set of input symbols, Γ is a finite set of pushdown symbols, δ is a mapping from Q×Σ λ ×Γ to finite subsets of Q × Γ * called the transition function, q 0 ∈ Q is the initial state, ⊥ ∈ Γ is the so-called bottom-of-pushdown symbol, which initially appears on the pushdown store, and F ⊆ Q is the set of accepting states.

A configuration of a pushdown automaton is a triple (q, w, γ), where q is the current state, w the unread part of the input, and γ the current content of the pushdown store, the leftmost symbol of γ being the top symbol. On input w the initial configuration is defined to be (q 0 , w, ⊥). If p, q are in Q, a is in Σ λ , w is in Σ * , γ and β are in Γ * , and Z is in Γ , then we write (q, aw, Zγ) M (p, w, βγ), if the pair (p, β) is in δ(q, a, Z). In order to simplify matters, we require that during any computation the bottom-of-pushdown symbol appears only at the bottom of the pushdown store. Formally, we require that if (p, β) is in δ(q, a, Z), then either β does not contain ⊥ or β = β ⊥, where β does not contain ⊥, and Z = ⊥. As usual, the reflexive transitive closure of M is denoted by * M . The subscript M will be dropped whenever the meaning remains clear. The language accepted by M with accepting states is

L(M ) = { w ∈ Σ * | (q 0 ,
w, ⊥) * (q, λ, γ), for some q ∈ F and γ ∈ Γ * }.

An NPDA is a deterministic pushdown automaton (DPDA), if there is at most one choice of action for any possible configuration. In particular, there must never be a choice of using an input symbol or of using λ input. Formally, a pushdown automaton M = Q, Σ, Γ, δ, q 0 , ⊥, F is deterministic if (i) δ(q, a, Z) contains at most one element, for all a in Σ λ , q in Q, and Z in Γ , and (ii) for all q in Q and Z in Γ : if δ(q, λ, Z) is not empty, then δ(q, a, Z) is empty for all a in Σ.

Now we turn to one-time nondeterministic pushdown automata (OTNPDA). As before, whenever such an automaton performs a guess, this guess is fixed for the rest of the computation. Let M = Q, Σ, Γ, δ, q 0 , ⊥, F be an NPDA and, for

q i ∈ Q, a i ∈ Σ λ , 0 ≤ i ≤ n, and Z i ∈ Γ , β i ∈ Γ * , 1 ≤ i ≤ n, (q 0 , a 0 w 0 , ⊥) M (q 1 , w 0 , β 1 ) = (q 1 , a 1 w 1 , Z 1 γ 1 ) M (q 2 , w 1 , β 2 γ 1 ) = (q 2 , a 2 w 2 , Z 2 γ 2 ) * M (q n , w n-1 , β n γ n-1 ) = (q n , a n w n , Z n γ n ) be a computation of M on input a 0 w 0 ∈ Σ + .
The computation is defined to be permissible if and only if, (i) the equality (q i , Z i ) = (q j , Z j ) implies either a i = a j = λ or a i = λ and a j = λ, and (ii) the equality (q i , a i , Z i ) = (q j , a j , Z j ) implies q i+1 = q j+1 and β i+1 = β j+1 , for all 0 ≤ i < j ≤ n -1. A word w is permissible acceptable by M if on input w there is an accepting permissible computation. The language accepted by an OTNPDA M is

L p (M ) = { w ∈ Σ * | word w is permissible acceptable by M }.
In order to derive the relationships of OTNPDAs, NPDAs, and DPDAs, we generalize the characterization of OTNFAs to pushdown automata. The notation as well as Theorem 3 is straightforwardly adapted. So, we obtain:

Theorem 8. Let M be a OTNPDA. Then L p (M ) = M ∈D(M ) L(M ), where D ne (M ) = { M | M is a DPDA with M ≺ ne M }.
So, the family of languages accepted by OTNPDAs is included in the (finite) union closure of the deterministic context-free languages. Conversely, the union of a finite number of languages accepted by DPDAs is accepted by an NPDA whose first transition is a nondeterministic choice of which of the DPDAs is to be simulated. Subsequently, the NPDA simulates the chosen DPDA. In this way, the nondeterministic situation at the beginning is never reached again and, thus, the NPDA is in fact a OTNPDA. We conclude that the union closure of the deterministic context-free languages is included in the family of languages accepted by OTNPDAs.

Corollary 9. The family of languages accepted by OTNPDAs and the union closure of the deterministic context-free languages are identical.

This characterization together with known results shows that the computational capacity of OTNPDAs is strictly in between the NPDAs and DPDAs. For establishing non-recursive trade-offs the following general result is useful that is a slightly generalized and unified form of a result of Hartmanis [START_REF] Hartmanis | On Gödel speed-up and succinctness of language representations[END_REF].

Theorem 11 ([9]). Let S 1 and S 2 be two descriptional systems for recursive languages such that any descriptor D in S 1 and S 2 can effectively be converted into a Turing machine that decides L(D), and let c 1 be a measure for S 1 and c 2 be an sn-measure for S 2 . If there exists a descriptional system S 3 and a property P that is not semi-decidable for descriptors from S 3 , such that, given an arbitrary D 3 ∈ S 3 , (i) there exists an effective procedure to construct a descriptor D 1 in S 1 , and (ii) D 1 has an equivalent descriptor in S 2 if and only if D 3 does not have property P , then the trade-off between S 1 and S 2 is non-recursive.

By measuring the amount of ambiguity and nondeterminism in pushdown automata in [START_REF] Herzog | Pushdown automata with bounded nondeterminism and bounded ambiguity[END_REF][START_REF] Herzog | Die Rolle des Nichtdeterminismus in kontextfreien Sprachen[END_REF] infinite hierarchies in between the deterministic and nondeterministic context-free languages are obtained. Intuitively, the corresponding language families are close together. Nevertheless, there are non-recursive tradeoffs between the levels of the hierarchies.

In the following we show non-recursive trade-offs between nondeterministic and OTNPDAs automata as well as between OTNPDAs deterministic pushdown automata by reduction from the non-halting problem for Turing machines on empty tape. To this end, histories of Turing machine computations are encoded into strings, a technique introduced in [START_REF] Hartmanis | Context-free languages and Turing machine computations[END_REF]. It suffices to consider deterministic Turing machines with one single tape and one single read-write head. Without loss of generality and for technical reasons, we assume that the Turing machines cannot print blanks, can halt only after an odd number of moves, accept by halting, and visit an infinite number of squares if they do not halt.

Let Q be the state set of some Turing machine M , where q 0 is the initial state, T ∩ Q = ∅ is the tape alphabet containing the blank symbol, and Σ ⊂ T is the input alphabet. Then a configuration of M can be written as a word of the form

T * QT * such that t 1 t 2 • • • t i qt i+1 • • • t n is used
to express that M is in state q, scanning tape symbol t i+1 , and t 1 , t 2 to t n is the support of the tape inscription. Dependent on the Turing machine M we define the following two languages. Let a, b, $, # / ∈ T ∪ Q, n ≥ 0, and w i ∈ T * QT * , 0 ≤ i ≤ 2n + 1 are configurations of M . Then language L M,0 contains all words of the form $w

0 $w R 1 $w 2 $w R 3 $ • • • $w 2n #w R 2n+1 #a
, where w 0 is an initial configuration with empty tape of the form w 0 = q 0 and w 2i is the successor configuration of w 2i-1 , 1 ≤ i ≤ n, and language L M,1 contains all words of the form

$w 0 $w R 1 $w 2 $w R 3 $ • • • $w 2n #w R 2n+1 #b
, where w 2i+1 is the successor configuration of w 2i , 0 ≤ i ≤ n. As an immediate observation we obtain the next corollary.

Corollary 12. For any deterministic Turing machine M , both languages L M,0 and L M,1 are deterministic context-free languages, such that their deterministic pushdown automata can effectively be constructed from M .

In order to apply Theorem 11, we use the family of deterministic one-tape Turing machines as descriptional system S 3 , and for the property P we take the property of not halting on empty tape. Recall that this property is indeed not semi-decidable for deterministic one-tape Turing machines. Next, given an arbitrary deterministic one-tape Turing machine M , that is, a descriptor D 3 ∈ S 3 , we must construct a nondeterministic pushdown automaton, that is, a descriptor D 1 in S 1 , that has an equivalent one-time nondeterministic pushdown automaton, that is, a descriptor in S 2 , if and only if M halts on empty tape.

So, given a deterministic one-tape Turing machine M , we use a new symbol c and define L M = ((L M,0 ∪ L M,1 )c) * . By Corollary 12 and the effective closures of the context-free languages under union and marked Kleene star, we derive that L M is a context-free language, such that its nondeterministic pushdown automaton D 1 can effectively be constructed from M . It remains to be shown that L M is accepted by a one-time nondeterministic pushdown automaton if and only if M halts on empty tape. The next lemma shows that L M is accepted even by a deterministic pushdown automaton if M halts on empty tape. Lemma 13. Let M be a deterministic Turing machine that halts on empty tape. Then language L M is accepted by some DPDA.

In order to disprove that L M is accepted by a OTNPDA if M does not halt on empty tape Ogden's lemma for deterministic context-free languages is used (see, for example, [START_REF] Harrison | Introduction to Formal Language Theory[END_REF]). Then one can show the following result. Lemma 14. Let M be a deterministic Turing machine that does not halt on empty tape. Then language L M is not accepted by any OTNPDA.

So, we have shown the following theorem.

Theorem 15. The trade-off between nondeterministic pushdown automata and one-time nondeterministic pushdown automata is non-recursive.

The proof of the second non-recursive trade-off between one-time nondeterministic pushdown automata and deterministic pushdown automata follows along the lines of the first non-recursive trade-off. Again, we apply Theorem 11 but now with a simplification of the language L M . More precisely, given a deterministic one-tape Turing machine M , we define L M = L M,0 ∪ L M,1 . By Corollary 12, both languages L M,0 and L M,1 are deterministic context-free languages, such that their deterministic pushdown automata can effectively be constructed from M . So, L M is accepted by a one-time nondeterministic pushdown automaton that can effectively be constructed from M . As before, it remains to be shown that L M is accepted by a deterministic pushdown automaton if and only if M halts on empty tape. If M halts on empty tape, Lemma 13 says that L M is accepted by some DPDA. Since the deterministic context-free languages are closed under intersection with regular sets, this implies that L M is accepted by some DPDA either.

Fig. 1 .

 1 Fig. 1. Left: the NFA M with a sole nondeterministic state accepting the language (a + b) * a(a + b). Interpreting M as an OTNFA results in accepting b * a(a + b). Middle: partial DFA M built from M by choosing the a-self-loop on the state 1 and deleting all other a-transitions leaving state 1. Right: partial DFA M built from M by choosing the a-transition from state 1 to 2 and deleting all other a-transitions from state 1.

Lemma 5 .

 5 Let M be an OTNFA. Then |D ne (M )| = d(M ).

Fig. 2 .

 2 Fig. 2. The transition function δ of the OTNFA M .

Theorem 10 .

 10 L (DPDA) ⊂ L (OTNPDA) ⊂ L (NPDA).

 Lemma 16. Let M be a deterministic Turing machine that does not halt on empty tape. Then language L M is not accepted by any DPDA.

Thus, we have also shown the following non-recursive trade-off.

Theorem 17. The trade-off between one-time nondeterministic pushdown automata and deterministic pushdown automata is non-recursive.


Raphael Tackx
email: raphael.tackx@lip6.fr

Fabien Tarissan
email: fabien.tarissan@ens-paris-saclay.fr

Jean-Loup Guillaume
email: jean-loup.guillaume@univ-lr.fr

COMSIM: A bipartite community detection algorithm using cycle and node's similarity

Keywords: Community detection, bipartite graph, social network

This study proposes COMSIM, a new algorithm to detect communities in bipartite networks. This approach generates a partition of nodes by relying on similarity between the nodes in terms of links towards ⊥ nodes. In order to show the relevance of this approach, we implemented and tested the algorithm on 2 small datasets equipped with a ground-truth partition of the nodes. It turns out that, compared to 3 baseline algorithms used in the context of bipartite graph, COMSIM proposes the best communities. In addition, we tested the algorithm on a large scale network. Results show that COMSIM has good performances, close in time to Louvain. Besides, a qualitative investigation of the communities detected by COMSIM reveals that it proposes more balanced communities.

Introduction

Many complex networks lend themselves to the use of graphs for analyzing and modelling their structure. Usually, vertices of the graph stand for the nodes of the network and the edges between vertices stand for (possible) interactions between nodes of the network. This approach has proven to be useful to identify non trivial properties of the structure of networks in very different contexts, ranging from computer science (the Internet, peer-to-peer networks, the web), to biology (protein-protein interaction networks, gene regulation networks), social science (friendship networks, collaboration networks), linguistics, economy, etc. [START_REF] Duncan | Collective dynamics of 'small-world' networks[END_REF][START_REF] Ferrer | The small world of human language[END_REF][START_REF] Mark Ej Newman | Random graph models of social networks[END_REF][START_REF] Battiston | Statistical properties of corporate board and director networks[END_REF][START_REF] Le Fessant | Clustering in peer-to-peer file sharing workloads[END_REF][START_REF] Prieur | The stength of weak cooperation: A case study on flickr[END_REF][START_REF] Ahn | Flavor network and the principles of food pairing[END_REF].

This abstraction into graphs allows in return to study formally different aspects of its structure. In this context, one question that has driven a lot of attention in the past decade is the identification of communities, that is sets of nodes that constitute cohesive groups inside the networks. Although no formal definition has led to a consensus in the scientific community, one usually assumes that members of a community should be more connected to each other than with the rest of the network. To identify such communities, one can rely on human expertise but, in the context of large-scale networks, the question of identifying automatically such communities has led to the proposition of several community detection algorithms [START_REF] Fortunato | Community detection in graphs[END_REF].

It is striking to notice that most algorithms have been designed for graphs containing only one set of nodes. Although useful, such a simple representation is not particularly close to the real structure of most of real networks. If one considers for instance an actor network that links actors performing in the same movies [START_REF] Duncan | Collective dynamics of 'small-world' networks[END_REF][START_REF] Mark Ej Newman | Random graphs with arbitrary degree distributions[END_REF] or co-authoring network that links authors publishing together [START_REF] Mark Ej Newman | Random graphs with arbitrary degree distributions[END_REF][START_REF] Mark Ej Newman | Random graph models of social networks[END_REF], one would rather relate actors to the movies they performed in and authors to their papers. This observation led the community to use bipartite graphs instead, i.e. graphs in which nodes can be divided into two disjoint sets, (e.g. movies) and ⊥ (e.g. actors), such that every link connects a node in to one in ⊥.

In that regard, only few community detection methods have been proposed to take into account this inherent bipartite complexity of real networks [START_REF] Liu | Community detection in large-scale bipartite networks[END_REF][START_REF] Daniel B Larremore | Efficiently inferring community structure in bipartite networks[END_REF][START_REF] Prat-Pérez | High quality, scalable and parallel community detection for large real graphs[END_REF]. The usual approach consists instead in projecting first the bipartite structure over one set of nodes and then applying standard community detection techniques. Although interesting, it has been shown that this approach suffers from limitations [START_REF] Lehmann | Biclique communities[END_REF].

Our contribution in this paper is to propose a new community detection algorithm dedicated to bipartite networks, namely COMSIM (Section 2). This algorithms relies on a measure of similarity between nodes exploiting the bipartite ties. Then the algorithm looks for cycles of connections maximizing the similarity between the nodes, thus defining the core of the communities.

In order to validate our approach, we rely on real dataset and compare the communities generated by our algorithm to baseline methods (Section 3). Results show that on dataset equipped with ground-truth communities, the communities inferred by COMSIM are the closest to the real ones. We also show that COMSIM obtains good results when applied on large-scale networks as it produces communities that are more homogeneous than the other approaches tested in this study.

New community detection algorithm: COMSIM

In this section, we formally presents our detection algorithm devoted to bipartite graphs. We first recall the necessary definitions (Section 2.1) before describing COMSIM algorithm (Section 2.2) and presenting baseline algorithms to which we compare our approach (Section 2.3).

Notations

A bipartite graph is defined by a triple B = ( , ⊥, E B ) (see Figure 1 for instance) where is the set of top nodes (e.g movies), ⊥ the set of bottom nodes (e.g. actors), and E b ⊆ × ⊥ the set of links between and ⊥ (that relates for instance the actors to the movies they perform in). Compared to unipartite graphs, nodes in a bipartite graph are separated in two disjoint sets, and the links are always between a node in one set and a node in the other set. But it is natural to also investigate how nodes from the same set are in relation. This approach is usually captured by the notion of projection of a bipartite graph over one of its two sets. For instance, if one is interested in the -projection, one can study how nodes connect according to their similarity measured by their links towards common ⊥ nodes. Formally, such a similarity is captured by a similarity function θ . This allows to formally define the weighted projected graph G = ( , θ ) where θ : × → R + . This graph thus indicates the strength of the relations between nodes. The -projection of the bipartite graph in Figure 1 will therefore result in the graph depicted Figure 2.

Note that in the rest of the paper, we will use the standard common neighbor function θ (x, y) = |N (x) ∩ N (y)|. But this approach easily extends to other similarity functions such as jaccard index [START_REF] Jaccard | Le coefficient generique et le coefficient de communaute dans la flore marocaine[END_REF], resource allocation [START_REF] Zhou | Predicting missing links via local information[END_REF] or adamic-adar coefficient [16]2 .

COMSIM algorithm

Given a bipartite graph B = ( , ⊥, E B ) and a similarity function θ such as common neighbors, COMSIM generate a partition of in two steps. First, it identifies the core communities, that are groups of nodes highly similar according to function θ .

As one can see in Algorithm 1 which details this first step, the algorithm generates a chain of nodes by following out-going links that have the highest weight according to θ . When this chain reaches a node already considered, it means that a cycle has been detected in the chain. This cycle then forms the core of a future community.

On the toy example of Figure 1, it would result in detecting that nodes A and B form the core of a community, as well as E and F. This is in accordance to Figure 2 which shows that A and B, as well as E and F have the highest weighted links. The other nodes (C and D) are left in the remaining set K.

The second phase of the algorithm then tries to position the remaining nodes of K in the existing communities by maximizing the similarity between these nodes and all the nodes of the core communities.

As described in Algorithm 2, the second step considers all remaining nodes that are not part of the partition after the first step. For each node x, it identifies the communities that have at least one link with x. The algorithm then chooses the community that maximizes the sum of similarities between x and all the nodes of the community.

On the toy example of Figure 1, and independently of the order in which nodes C and D are considered during step 2, it would result in affecting node C to the community A -B (the sum of similarities is 3) and node D to community E -F (the sum of similarities is 4).

It is worth noticing that because several links can have a similar weight, the two steps might face several equal options. In that case, the algorithm selects one option uniformly at random among all possible ones. For this reason, the algorithm is undeterministic and several runs might end up with different partitions.

Standard approaches

In order to evaluate the relevance of COMSIM, we will compare the detected communities with the ones of the three baseline detection algorithms described below.

Louvain: Louvain algorithm [START_REF] Vincent D Blondel | Fast unfolding of communities in large networks[END_REF] is a greedy algorithm that optimizes a quality function in order to extract communities from large unipartite networks. It is commonly used with modularity [START_REF] Mark Ej Newman | Modularity and community structure in networks[END_REF] which measures the density of the communities compared to their expected density if the links were randomly distributed over the network.

In order to evaluate Louvain's performance, and for fair comparison, we first project the bipartite graph over the nodes, generating a weighted graph according to the similarity function θ (common neighbor in our case). Then we apply Louvain on the weighted graph. Infomap: Infomap is a recursive algorithm, similar to Louvain, where each node is moved to a neighboring community if this modification minimizes the length of the map equation [START_REF] Rosvall | The map equation[END_REF]. Infomap can account for the bipartite structure and we use this feature to generate a partition of nodes only.

LPBRIM:

LPBRIM [START_REF] Liu | Community detection in large-scale bipartite networks[END_REF] is a community detection algorithm that optimizes the bimodularity [START_REF] Barber | Modularity and community detection in bipartite networks[END_REF] which is an extension of the modularity for bipartite graphs. It relies on BRIM algorithm (Bipartite, Recursively Induced Modules) and uses a label propagation procedure. Because LPBRIM provides a partition of the complete bipartite networks -communities are composed of and ⊥ nodes -, we adapt the algorithm and define a community by keeping only the nodes of the partitions. This allows a fair comparison in the evaluation process.

Evaluation of COMSIM

This section is devoted to assess the relevance of the proposed method. We start by investigating how the different algorithms behave on two small networks equipped with existing communities (Section 3.1) before showing how COMSIM scales up when dealing with large-scale networks (Section 3.2).

On dataset with ground-truth communities

We first apply our algorithm to two networks which are small but are provided with a notion of ground-truth communities that we use as a reference to compare the four algorithms.

Southern women [START_REF] Davis | Deep South; a Social Anthropological Study of Caste and Class[END_REF] is a network depicting the participation of 18 women to 14 events in the United States observed during a nine-months period in 1930. Although small, this dataset is very interesting since it has been extensively studied by social scientists to understand how social groups form and evolve (see [START_REF] Green | Southern strategies: Southern women and the woman suffrage question[END_REF][START_REF] Linton C Freeman | Finding social groups: A meta-analysis of the southern women data[END_REF] for instance). In this study, we use the partition found in the literature as the ground-truth communities to which we compare the four algorithms. 20 newsgroups [START_REF] Lang | Newsweeder: Learning to filter netnews[END_REF] is a record of approximately 50 000 posts submitted by 30 000 users (bot) over 20 groups of discussion ( ).

Figure 3 presents the results of the comparison between COMSIM and the three baseline algorithms for bipartite community detection described in Section 2.3. All algorithms were applied on Southern Women and 20 newsgroups dataset 100 times. The box plots provides the maximal, minimal and average values.

Since we have a ground-truth partition for the dataset, we use first the usual Normalized Mutual Information (NMI, see [START_REF] Lancichinetti | Detecting the overlapping and hierarchical community structure in complex networks[END_REF] for instance) to compute how far the detected partitions are from the ground-truth ones. Figure 3a reveals that for both datasets COMSIM is the algorithm that proposes the best partition in average. One can also notice that Infomap and LPBRIM generate good partitions for 20 newsgroups and Louvain good partitions for Southern Women.

It is interesting to notice that Infomap completely fails to detect the expected communities for Southern Women. Manual investigation revealed that all women of Southern Women are actually gathered in a single community, which is well captured by NMI (NMI= 0). On the opposite, each node of 20 newsgroups is positioned in a different community, which is completely overestimated by the NMI (NMI= 0.7643).

In order to provide a second point of view, we also use the F1-score, a classical metric to evaluate the performance of prediction algorithms (see [START_REF] Yang | Overlapping community detection at scale: a nonnegative matrix factorization approach[END_REF] for an example of F1-score used in the context of community detection issues). Figure 3b shows again that COMSIM is the best community detection algorithm for both datasets in average. Interestingly, for this metric, Louvain seems to propose good partitions in average and for both dataset.

All in all, it seems that COMSIM proposes coherent communities when compared to ground-truth partitions of bipartite networks. The next section intends to investigate how the algorithm behaves on a large scale network.

On large-scale networks

In order to test the performance of our algorithm both in terms of efficiency and quality, we rely here on a large dataset extracted from the Internet Movie Database (IMDb). This dataset [START_REF] Maas | Learning word vectors for sentiment analysis[END_REF] Table 1 presents the performances in terms of execution time and memory peak for the four algorithms on the three datasets. This shows that Louvain remains the most efficient algorithm in terms both of time and memory, revealing to be slower only on the smallest dataset.

However, it should be highlighted here that the performances of Louvain shown in Table 1 have been recorded after the -projection. This means that part of the computation load related to the θ function has been avoided, which is not the case for the other algorithms. It thus mechanically favour the Louvain approach.

To that regard, it is worth noticing that our algorithm presents good results. On IMDb in particular, COMSIM is only slightly slower than Louvain and three times faster than Infomap.

The results above show that our algorithm can scale up to large networks but that it provides no insight on the quality of the detected communities. In contrast to the previous section where we had ground-truth knowledge of the good partitions, no study conducted on the IMDb dataset proposes an objective and external partition of the nodes. It is thus impossible to use here either NMI or F1-score to compare the three remaining algorithms 4 .

In order to assess the quality of the proposed communities, we follow instead the proposition made in [START_REF] Yang | Defining and evaluating network communities based on ground-truth[END_REF] where the authors introduce two goodness functions in an attempt to quantify how relevant a community is regarding two properties that we adapted for the case of bipartite graphs: the Density (or Internal Density) and Separability. More formally, let P be a partition of nodes. Given a community C i ∈ P, we denote by C i =

x i ∈C i N(x i ) the set of ⊥ nodes induced by the neighborhood of C i . Let m C i be the number of edges between C i and C i (internal number of edges) and m C i the number of edges between C i and C j (external number of edges), where j = i. Then we define the internal density and the separability as follow:

• Internal Density of community C i :

m C i |C i | * |C i | • Separability of community C i : m C i m C i +m C i
Those two indicators allow to evaluate how coherent a community is regarding internal and external edges. Figure 4 presents the distribution of the Internal Density (Figure 4a) and the Separability (Figure 4b) of communities according to their size and for the three algorithms (COMSIM top, Louvain middle and Infomap bottom).

This shows that Infomap mostly fails to detect coherent communities. Indeed, although most of the communities have very high values for both properties, it concerns mostly very little communities composed of few nodes. But for large communities, the indicators drop. This is particularly obvious on Figure 4a. To that regard, it is striking to notice that the largest community detected by Infomap gathers more than 46% of the nodes and the 7 largest communities involve more than 96% of the nodes. The same observation can be made for Louvain, although to a lesser extent. The largest community involves 29% (48% for the 7 largest communities).

Compared to Louvain and Infomap, COMSIM proposes more balanced communities in terms of size. The largest community is rather small (only 1% of the nodes) while keeping a profile of density close to the ones of Louvain (see Figure 4a). Regarding the separability however, there is a slight shift towards low values compared to Louvain, which indicates that the quality of the partitions could be improved for this property.

All in all, an although more experiments should be made in order to complete the comparison, we claim that this study is a first step establishing the relevance of the proposed approach, both in terms of efficiency and quality of the detected communities.

Conclusions

In this study we proposed COMSIM, a new algorithm to detect community in bipartite networks. This approach generates a partition of the nodes by relying on similarity between the nodes in terms of connections towards ⊥ nodes. To do so, it tries to find and maximize cycles of relations between nodes. This defines the core of the communities which are enriched with new nodes during a second phase of the algorithm.

We implemented and applied this algorithm on 3 datasets and compared the generated partitions with the ones proposed by three baseline algorithms used on bipartite graphs. The empirical results showed that, on small networks for which we had a ground-truth knowledge of the good partition, COMSIM is the algorithm that generates the best communities.

In addition, COMSIM proved to scale up with a time complexity close to Louvain. Investigating qualitatively the partitions, we showed that the communities generated by COMSIM are more balanced in terms of size, while keeping quality indicators reasonable and comparable to the ones proposed by Louvain for instance.

It is worth noticing that other algorithms could have been used for the comparison. For instance, biSBM [START_REF] Daniel B Larremore | Efficiently inferring community structure in bipartite networks[END_REF] or SCD [START_REF] Prat-Pérez | High quality, scalable and parallel community detection for large real graphs[END_REF] are relevant, although not completely adapted to this context. The former requires to provide the number of expected communities, while the latter proposes overlapping communities.

We claim that this study establishes the relevance of the approach and we let more in-depth study for future work.

Fig. 1

 1 Fig. 1 Example of a bipartite graph B = ( , ⊥, E B ).

Fig. 2

 2 Fig. 2 Example of the weighted -projection of B using common neighbors as similarity function.

Algorithm 1 :

 1 COMSIM-first stepData: a bipartite graph B = ( , ⊥, E B ), a similarity function θ Result: return a partition P of nodes and a set K of remaining nodes (for the second step) P := / 0 // the partition set T := // the set of nodes to be considered x := rand and remove(T ) // random node V := / 0 // set of nodes currently consideredK := / 0 // set of remaining nodes while T = / 0 do /* finds a neighbor y ∈ N 2 (x) of x maximizing θ (x, y) */ y := argmax y∈N 2 (x) θ (x, y) if y ∈ V then C := cycle(V,y, x) // extract the detected cycle from y to x in V P.add(C) K := K ∪ (V -C) // stores nodes not in the cycle C V := / 0 x := rand and remove(T ) else if y ∈ T then V := V ∪ {y} x := y T := T -{y} else /* y is already part of an element of P, visited nodes are stored */ K := K ∪V V := / 0 x := rand and remove(T ) return P and K Algorithm 2: COMSIM-second step Data: a bipartite graph B = ( , ⊥, E B ); a partition P; a set K of remaining nodes (from first step), a similarity function θ . Result: return a partition P of nodes and unsatisfied nodes R R := / 0 // Remaining nodes P := P foreach x ∈ K do P x := com neigh(x, P) // Find all neighbor communities of x if P x = / 0 then R := R ∪ {x} else C := argmax Cx∈Px ∑ y∈Cx θ (x, y) Add x into the partition C of P return P and R

Fig. 3

 3 Fig.3Evaluation of the quality of the partitions detected by the algorithms on 20 newsgroups and Southern Women.

Fig. 4

 4 Fig. 4 Scatter plot displaying the relation between properties of the communities and their size for COMSIM (top), Louvain (middle) and Infomap (bottom) on IMDb.

Table 1

 1 presents a bipartite network composed of 118 258 actors (⊥) who played in 122 131 movies ( ) between 1980 and 20103 . Performances in terms of execution time and peak for the four algorithms.

		Southern women 20 newsgroups	IMDb
	| |/|⊥|/links	18/14/89	20/30K/42K 122K/118K/531K
	COMSIM	1.7 ms / 11.5 MB 1.1 s / 30 MB 33.5 s / 591.6 MB
	Infomap	13 ms / 10.7 MB 951 ms / 6.3 MB 100s / 374 MB
	Louvain	11 ms / 6.5 MB 86 ms / 10.1 MB 21 s / 43 MB
	LPBRIM	6.7 s / 6.1 MB 74.2 s / 59.7MB	-/-

We use a similar definition of N ⊥ (v) for v ∈ ⊥.

Depending on the similarity function used, the projection might result in a directed weighted graph if θ is not symmetric.

For an homogeneous analysis, we removed all TV shows and documentaries and kept only the 7 first actors listed in the casting.

Since LPBRIM does not scale up to the size of IMDb, we avoid mentioning this approach in the rest of the study.

Acknowledgements

This work is funded in part by the European Commission H2020 FETPROACT 2016-2017 program under grant 732942 (ODYCCEUS), by the ANR (French National Agency of Research) under grants ANR-15-CE38-0001 (AlgoDiv) and ANR-13-CORD-0017-01 (CODDDE), by the French program "PIA -Usages, services et contenus innovants" under grant O18062-44430 (REQUEST), and by the Ile-de-France program FUI21 under grant 16010629 (iTRAC).