(self, paths, k=1, separator='-', nullModel=False, method='FirstOrderTransitions', lanczosVecs=15, maxiter=1000)
Generates a k-th-order representation based on the given path statistics.

        @param paths: An instance of class Paths, which contains the path statistics to be 
            used in the generation of the k-th order representation 

        @param k: The order of the network representation to generate. For the default case of 
            k=1, the resulting representation corresponds to the usual (first-order) aggregate network, 
            i.e. links connect nodes and link weights are given by the frequency of each interaction. For 
            k>1, a k-th order node corresponds to a sequence of k nodes. The weight of a k-th order link 
            captures the frequency of a path of length k.

        @param separator: The separator character to be used in higher-order node names.

        @param nullModel: For the default value False, link weights are generated based on the statistics of 
            paths of length k in the underlying path statistics instance. If True, link weights are generated 
            from the first-order model (k=1) based on the assumption of independent links (i.e. corresponding) 
            to a first-order Markov model.

        @param method: specifies how the null model link weights in the k-th order model are calculated. 
            For the default method='FirstOrderTransitions', the weight w('v_1-v_2-...v_k', 'v_2-...-v_k-v_k+1') of 
            a k-order edge is set to the transition probability T['v_k', 'v_k+1'] in the first order network.
            For method='KOrderPi' the entry pi['v1-...-v_k'] in the stationary distribution of the 
            k-order network is used instead.
Generates a k-th-order representation based on the given path statistics.
Generates a k - th - order representation based on the given path statistics .
def __init__(self, paths, k=1, separator='-', nullModel=False, method='FirstOrderTransitions', lanczosVecs=15, maxiter=1000):
        """
        Generates a k-th-order representation based on the given path statistics.

        @param paths: An instance of class Paths, which contains the path statistics to be 
            used in the generation of the k-th order representation 

        @param k: The order of the network representation to generate. For the default case of 
            k=1, the resulting representation corresponds to the usual (first-order) aggregate network, 
            i.e. links connect nodes and link weights are given by the frequency of each interaction. For 
            k>1, a k-th order node corresponds to a sequence of k nodes. The weight of a k-th order link 
            captures the frequency of a path of length k.

        @param separator: The separator character to be used in higher-order node names.

        @param nullModel: For the default value False, link weights are generated based on the statistics of 
            paths of length k in the underlying path statistics instance. If True, link weights are generated 
            from the first-order model (k=1) based on the assumption of independent links (i.e. corresponding) 
            to a first-order Markov model.

        @param method: specifies how the null model link weights in the k-th order model are calculated. 
            For the default method='FirstOrderTransitions', the weight w('v_1-v_2-...v_k', 'v_2-...-v_k-v_k+1') of 
            a k-order edge is set to the transition probability T['v_k', 'v_k+1'] in the first order network.
            For method='KOrderPi' the entry pi['v1-...-v_k'] in the stationary distribution of the 
            k-order network is used instead.
        """

        assert nullModel == False or (nullModel and k>1)

        assert method == 'FirstOrderTransitions' or method == 'KOrderPi', 'Error: unknown method to build null model'

        assert len(paths.paths.keys())>0 and max(paths.paths.keys())>=k, 'Error: constructing a model of order k requires paths of at least length k'
        
        ## The order of this HigherOrderNetwork
        self.order = k

        ## The paths object used to generate this instance
        self.paths = paths

        ## The nodes in this HigherOrderNetwork 
        self.nodes = []

        ## The separator character used to label higher-order nodes. 
        ## For separator '-', a second-order node will be 'a-b'.
        self.separator = separator

        ## A dictionary containing edges as well as edge weights
        self.edges = _co.defaultdict( lambda: _np.array([0,0]) )

        ## A dictionary containing the sets of successors of all nodes
        self.successors = _co.defaultdict( lambda: set() )

        ## A dictionary containing the sets of predecessors of all nodes
        self.predecessors = _co.defaultdict( lambda: set() )

        if k>1: 
            # For k>1 we need the first-order network to generate the null model
            # and calculate the degrees of freedom

            # For a multi-order model, the first-order network is generated multiple times!
            # TODO: Make this more efficient
            g1 = HigherOrderNetwork(paths, k=1)
            A = g1.getAdjacencyMatrix(includeSubPaths = True, weighted=False, transposed=True)

        if not nullModel:
            # Calculate the frequency of all paths of
            # length k, generate k-order nodes and set
            # edge weights accordingly
            for p in paths.paths[k]:
                # For a 0-order model, we generate a dummy start node
                if k==0: 
                    v = 'start'
                    w = p[0]
                else:
                    # Generate names of k-order nodes v and w
                    v = p[0]
                    w = p[1]
                    for l in range(1, k):
                        v = v + separator + p[l]
                        w = w + separator + p[l+1]
                self.nodes.append(v)
                self.nodes.append(w)

                # as edge weights of the k-th order model, we sum the
                # occurrence of paths of length k as subpath and longest path
                self.edges[(v,w)] += paths.paths[k][p]
                self.successors[v].add(w)
                self.predecessors[w].add(v)
            self.nodes = list(set(self.nodes)) # removes duplicates, does however randomize the order
            # Note: For all sequences of length k which (i) have never been observed, but (ii) 
            #       do actually represent paths of length k in the first-order network, we 
            #       may want to include some 'escape' mechanism along the lines of (Cleary and Witten 1994)                        

        else:
            # generate the *expected* frequencies of all possible 
            # paths based on independently occurring (first-order) links
            
            # generate all possible paths of length k 
            # based on edges in the first-order network
            possiblePaths = list(g1.edges.keys())

            E_new = list()
            for e1 in possiblePaths:
                for e2 in g1.edges:
                    if e1[-1] == e2[0]:
                        p = e1 + (e2[1],)
                        E_new.append(p)
            possiblePaths = E_new

            # validate that the number of unique generated paths corresponds to the sum of entries in A**k            
            assert (A**k).sum() == len(possiblePaths), 'Expected ' + str((A**k).sum()) + ' paths but got ' + str(len(possiblePaths))
            
            if method == 'KOrderPi':
                # compute stationary distribution of a random walker in the k-th order network
                g_k = HigherOrderNetwork(paths, k=k, separator = separator, nullModel = False)
                pi_k = HigherOrderNetwork.getLeadingEigenvector(g_k.getTransitionMatrix(includeSubPaths=True), normalized=True, lanczosVecs=lanczosVecs, maxiter=maxiter)
            else:
                # A = g1.getAdjacencyMatrix(includeSubPaths=True, weighted=True, transposed=False)
                T = g1.getTransitionMatrix(includeSubPaths=True)

            # assign link weights in k-order null model
            for p in possiblePaths:
                v = p[0]   
                w = p[1]
                # add k-order nodes and edges
                for l in range(1, k):
                    v = v + separator + p[l]
                    w = w + separator + p[l+1]
                self.nodes.append(v)
                self.nodes.append(w)

                # NOTE: under the null model's assumption of independent events, we
                # have P(B|A) = P(A ^ B)/P(A) = P(A)*P(B)/P(A) = P(B)
                # In other words: we are encoding a k-1-order Markov process in a k-order
                # Markov model and for the transition probabilities T_AB in the k-order model 
                # we simply have to set the k-1-order probabilities, i.e. T_AB = P(B)
                
                # Solution A: Use entries of stationary distribution, 
                # which give stationary visitation frequencies of k-order node w
                if method == 'KOrderPi':
                    self.edges[(v,w)] = _np.array( [ 0, pi_k[ g_k.nodes.index(w) ] ] )

                # Solution B: Use relative edge weight in first-order network
                # Note that A is *not* transposed
                # self.edges[(v,w)] = A[(g1.nodes.index(p[-2]),g1.nodes.index(p[-1]))] / A.sum()

                # Solution C: Use transition probability in first-order network
                # Note that T is transposed (!)
                elif method == 'FirstOrderTransitions':
                    p_vw = T[ ( g1.nodes.index(p[-1]), g1.nodes.index(p[-2]) ) ]
                    self.edges[(v,w)] =  _np.array( [0, p_vw] )  

                # Solution D: calculate k-path weights based on entries of squared k-1-order adjacency matrix

                # Note: Solution B and C are equivalent
                self.successors[v].add(w)
            self.nodes = list(set(self.nodes))

        # Compute degrees of freedom of models
        if k==0:
            # for a zero-order model, we just fit node probabilities (excluding the special 'start' node) 
            # Since probabilities must sum to one, the effective degree of freedom is one less than the number of nodes
            # This holds for both the paths and the ngrams model
            self.dof_paths = self.vcount() - 2
            self.dof_ngrams = self.vcount() - 2
        else:
            # for a first-order model, self is the first-order network
            if k==1:
                g1 = self
                A = g1.getAdjacencyMatrix(includeSubPaths = True, weighted=False, transposed=True)
           
            # Degrees of freedom in a higher-order ngram model
            s = g1.vcount()

            ## The degrees of freedom of the higher-order model, under the ngram assumption
            self.dof_ngrams = (s**k)*(s-1)
                 
            # For k>0, the degrees of freedom of a path-based model depend on 
            # the number of possible paths of length k in the first-order network.
            # Since probabilities in each row must sum to one, the degrees 
            # of freedom must be reduced by one for each k-order node 
            # that has at least one possible transition.

            # (A**k).sum() counts the number of different paths of exactly length k
            # based on the first-order network, which corresponds to the number of 
            # possible transitions in the transition matrix of a k-th order model. 
            paths_k = (A**k).sum()

            # For the degrees of freedom, we must additionally consider that 
            # rows in the transition matrix must sum to one, i.e. we have to 
            # subtract one degree of freedom for every non-zero row in the (null-model)
            # transition matrix. In other words, we subtract one for every path of length k-1 
            # that can possibly be followed by at least one edge to a path of length k

            # This can be calculated by counting the number of non-zero elements in the 
            # vector containing the row sums of A**k
            non_zero = _np.count_nonzero((A**k).sum(axis=0))

            ## The degrees of freedom of the higher-order model, under the paths assumption
            self.dof_paths = paths_k - non_zero
def __init__ ( self , paths , k = 1 , separator = '-' , nullModel = False , method = 'FirstOrderTransitions' , lanczosVecs = 15 , maxiter = 1000 ) : assert nullModel == False or ( nullModel and k > 1 ) assert method == 'FirstOrderTransitions' or method == 'KOrderPi' , 'Error: unknown method to build null model' assert len ( paths . paths . keys ( ) ) > 0 and max ( paths . paths . keys ( ) ) >= k , 'Error: constructing a model of order k requires paths of at least length k' ## The order of this HigherOrderNetwork self . order = k ## The paths object used to generate this instance self . paths = paths ## The nodes in this HigherOrderNetwork  self . nodes = [ ] ## The separator character used to label higher-order nodes.  ## For separator '-', a second-order node will be 'a-b'. self . separator = separator ## A dictionary containing edges as well as edge weights self . edges = _co . defaultdict ( lambda : _np . array ( [ 0 , 0 ] ) ) ## A dictionary containing the sets of successors of all nodes self . successors = _co . defaultdict ( lambda : set ( ) ) ## A dictionary containing the sets of predecessors of all nodes self . predecessors = _co . defaultdict ( lambda : set ( ) ) if k > 1 : # For k>1 we need the first-order network to generate the null model # and calculate the degrees of freedom # For a multi-order model, the first-order network is generated multiple times! # TODO: Make this more efficient g1 = HigherOrderNetwork ( paths , k = 1 ) A = g1 . getAdjacencyMatrix ( includeSubPaths = True , weighted = False , transposed = True ) if not nullModel : # Calculate the frequency of all paths of # length k, generate k-order nodes and set # edge weights accordingly for p in paths . paths [ k ] : # For a 0-order model, we generate a dummy start node if k == 0 : v = 'start' w = p [ 0 ] else : # Generate names of k-order nodes v and w v = p [ 0 ] w = p [ 1 ] for l in range ( 1 , k ) : v = v + separator + p [ l ] w = w + separator + p [ l + 1 ] self . nodes . append ( v ) self . nodes . append ( w ) # as edge weights of the k-th order model, we sum the # occurrence of paths of length k as subpath and longest path self . edges [ ( v , w ) ] += paths . paths [ k ] [ p ] self . successors [ v ] . add ( w ) self . predecessors [ w ] . add ( v ) self . nodes = list ( set ( self . nodes ) ) # removes duplicates, does however randomize the order # Note: For all sequences of length k which (i) have never been observed, but (ii)  #       do actually represent paths of length k in the first-order network, we  #       may want to include some 'escape' mechanism along the lines of (Cleary and Witten 1994)                         else : # generate the *expected* frequencies of all possible  # paths based on independently occurring (first-order) links # generate all possible paths of length k  # based on edges in the first-order network possiblePaths = list ( g1 . edges . keys ( ) ) E_new = list ( ) for e1 in possiblePaths : for e2 in g1 . edges : if e1 [ - 1 ] == e2 [ 0 ] : p = e1 + ( e2 [ 1 ] , ) E_new . append ( p ) possiblePaths = E_new # validate that the number of unique generated paths corresponds to the sum of entries in A**k             assert ( A ** k ) . sum ( ) == len ( possiblePaths ) , 'Expected ' + str ( ( A ** k ) . sum ( ) ) + ' paths but got ' + str ( len ( possiblePaths ) ) if method == 'KOrderPi' : # compute stationary distribution of a random walker in the k-th order network g_k = HigherOrderNetwork ( paths , k = k , separator = separator , nullModel = False ) pi_k = HigherOrderNetwork . getLeadingEigenvector ( g_k . getTransitionMatrix ( includeSubPaths = True ) , normalized = True , lanczosVecs = lanczosVecs , maxiter = maxiter ) else : # A = g1.getAdjacencyMatrix(includeSubPaths=True, weighted=True, transposed=False) T = g1 . getTransitionMatrix ( includeSubPaths = True ) # assign link weights in k-order null model for p in possiblePaths : v = p [ 0 ] w = p [ 1 ] # add k-order nodes and edges for l in range ( 1 , k ) : v = v + separator + p [ l ] w = w + separator + p [ l + 1 ] self . nodes . append ( v ) self . nodes . append ( w ) # NOTE: under the null model's assumption of independent events, we # have P(B|A) = P(A ^ B)/P(A) = P(A)*P(B)/P(A) = P(B) # In other words: we are encoding a k-1-order Markov process in a k-order # Markov model and for the transition probabilities T_AB in the k-order model  # we simply have to set the k-1-order probabilities, i.e. T_AB = P(B) # Solution A: Use entries of stationary distribution,  # which give stationary visitation frequencies of k-order node w if method == 'KOrderPi' : self . edges [ ( v , w ) ] = _np . array ( [ 0 , pi_k [ g_k . nodes . index ( w ) ] ] ) # Solution B: Use relative edge weight in first-order network # Note that A is *not* transposed # self.edges[(v,w)] = A[(g1.nodes.index(p[-2]),g1.nodes.index(p[-1]))] / A.sum() # Solution C: Use transition probability in first-order network # Note that T is transposed (!) elif method == 'FirstOrderTransitions' : p_vw = T [ ( g1 . nodes . index ( p [ - 1 ] ) , g1 . nodes . index ( p [ - 2 ] ) ) ] self . edges [ ( v , w ) ] = _np . array ( [ 0 , p_vw ] ) # Solution D: calculate k-path weights based on entries of squared k-1-order adjacency matrix # Note: Solution B and C are equivalent self . successors [ v ] . add ( w ) self . nodes = list ( set ( self . nodes ) ) # Compute degrees of freedom of models if k == 0 : # for a zero-order model, we just fit node probabilities (excluding the special 'start' node)  # Since probabilities must sum to one, the effective degree of freedom is one less than the number of nodes # This holds for both the paths and the ngrams model self . dof_paths = self . vcount ( ) - 2 self . dof_ngrams = self . vcount ( ) - 2 else : # for a first-order model, self is the first-order network if k == 1 : g1 = self A = g1 . getAdjacencyMatrix ( includeSubPaths = True , weighted = False , transposed = True ) # Degrees of freedom in a higher-order ngram model s = g1 . vcount ( ) ## The degrees of freedom of the higher-order model, under the ngram assumption self . dof_ngrams = ( s ** k ) * ( s - 1 ) # For k>0, the degrees of freedom of a path-based model depend on  # the number of possible paths of length k in the first-order network. # Since probabilities in each row must sum to one, the degrees  # of freedom must be reduced by one for each k-order node  # that has at least one possible transition. # (A**k).sum() counts the number of different paths of exactly length k # based on the first-order network, which corresponds to the number of  # possible transitions in the transition matrix of a k-th order model.  paths_k = ( A ** k ) . sum ( ) # For the degrees of freedom, we must additionally consider that  # rows in the transition matrix must sum to one, i.e. we have to  # subtract one degree of freedom for every non-zero row in the (null-model) # transition matrix. In other words, we subtract one for every path of length k-1  # that can possibly be followed by at least one edge to a path of length k # This can be calculated by counting the number of non-zero elements in the  # vector containing the row sums of A**k non_zero = _np . count_nonzero ( ( A ** k ) . sum ( axis = 0 ) ) ## The degrees of freedom of the higher-order model, under the paths assumption self . dof_paths = paths_k - non_zero