2
$\begingroup$

The standard setup of a Totally Asymmetric Simple Exclusion Process is pictured below:

TASEP

We have a one-dimensional lattice of length $n$ populated with particles($p_1,p_2,p_3$ in this case) that hop to the right, but only if the neighboring cell contains no particle($p_1$ may hop, but $p_2$ may not). Each particle independently waits a random amount of (continuous-)time before trying to hop. Particles are injected into the lattice at rate $r_i$ as long as the first cell is empty and ejected from the lattice at rate $r_e$ as long as the last cell is full.

Instead of a lattice, one can instead create an equivalent TASEP on a simple directed graph:

Graph TASEP

The green edges represent our particles. One can picture the "particles" hopping like so:

Head Move

And they may hop as long as no edge is in the way. Alternatively, we could have:

Graph TASEP

Here, the tails move along the purple path instead of the heads. (See A polytree game.)

Now we generalize our TASEP by treating our "lattice" exactly as if it was just made up of particles all along. We allow any edge to hop independently. If an edge has multiple possible hops, it chooses one at random. We allow any edge to be added to the graph between any two nodes at rate $r_i$ (if no edge exists between those two nodes) and any edge to be deleted from the graph at rate $r_e$ (if the edge exists between two random nodes) all while the edges independently head-move or tail-move.

We have several questions about this process:

  • Given a random directed graph on $n$ nodes, what are the steady states of this process as we vary $r_i$ and $r_e$?
  • What's the hitting time of these states?
  • For large $n$ and as time $\rightarrow \infty$, what's the expected degree distribution(example below)?
  • Besides the degree distribution, what other measures of the resultant graphs differ significantly from random graphs?

Degree distribution starting from 5000 node graph with edge probability = .0008 after 500000 hops:

Degree Distribution

This distribution is from a discrete-time version I've implemented. Here's the code if you'd like to explore this process yourself:

import networkx as nx
import matplotlib.pyplot as plt
from random import choice,choices,random

"""
hmove in:  source --> target1 --> target2
hmove out: source --> target2 <-- target1
"""
def hmove(G, source, target1, target2): #Head move
    G.remove_edge(source, target1)
    G.add_edge(source, target2)
#Return a list of all possible head moves for the edge (source, target1).
def list_hmoves(G, source, target1):
    hmove_list=[]
    for target2 in G.neighbors(target1):
        if not G.has_edge(source, target2):
            hmove_list.append([hmove, source, target1, target2])
    return hmove_list
"""
tmove in:  target1 <-- source --> target2
tmove out: source --> target2 --> target1
"""
def tmove(G, source, target1, target2): #Tail move
    G.remove_edge(source, target1)
    G.add_edge(target2, target1)
#Return a list of all possible tail moves for the edge (source, target1).    
def list_tmoves(G, source, target1):
    tmove_list=[]
    for target2 in G.neighbors(source):
        if target1==target2:
            continue
        if not G.has_edge(target2, target1):
            tmove_list.append([tmove, source, target1, target2])
    return tmove_list

#Return a list of all available moves for the edge (source, target1).
def list_moves(G, source, target1):
    move_list=[]
    move_list.extend(list_hmoves(G, source, target1))
    move_list.extend(list_tmoves(G, source, target1))
    return move_list

#Degree Histogram
def degree_histogram(G, filename):
    out_degrees=[G.out_degree(node) for node in G.nodes()]
    in_degrees=[G.in_degree(node) for node in G.nodes()]
    bins=range(min(min(out_degrees),min(in_degrees)), max(max(out_degrees),max(in_degrees))+1,)
    plt.hist(out_degrees, bins, alpha=0.5, color = 'red')
    plt.hist(in_degrees, bins, alpha=0.5, color = 'blue')
    plt.title('Degree Histogram: In = Blue, Out = Red' + '\n' +'Injection = {} Ejection = {}'.format(injection_rate, ejection_rate))
    #plt.savefig(filename, bbox_inches='tight')
    plt.show()

#Draw Graph
def draw_graph(G, filename):
    nx.draw(G, pos=nx.circular_layout(G), node_color='black', node_size=20)
    plt.title('Injection Rate is {} Ejection Rate is {}, {} hops'.format(injection_rate, ejection_rate, hops) + '\n' + 'Graph Density is {}'.format(G.size()/G.order()**2))
    #plt.savefig(filename, bbox_inches='tight')
    plt.show()

def init_graph(number_of_nodes=5000, edge_probability=.0008):
    #Build our digraph.  Note we don't mind self-loops!
    G=nx.gnp_random_graph(number_of_nodes,edge_probability, None, True)
    return G

def main(G):
    #Main Loop
    for i in range(hops):
        if random()<injection_rate:                  #Try to add an edge with probability equal to injection_rate
            random_edge=choices(list(G.nodes()),k=2) #Pick a (possibly non-existant) edge at random
            if not G.has_edge(*random_edge):         #This does nothing if G already contains random_edge
                G.add_edge(*random_edge)  
        if random()<ejection_rate:                   #Attempt to delete an edge with probability equal to ejection_rate
            random_edge=choices(list(G.nodes()),k=2) #Pick a (possibly non-existant) edge at random
            if G.has_edge(*random_edge):             #This does nothing if G doesn't contain random_edge
                G.remove_edge(*random_edge)    
        if G.size()>0:                               #Check if there are edges.
            random_edge=choice(list(G.edges()))      #Pick an edge at random.
            move_list=list_moves(G, *random_edge)    #List of all possible moves of random_edge
            if len(move_list)>0:                     #Check if edge has moves.
               random_move=choice(move_list)         #Make a random move.
               random_move[0](G, *random_move[1:])
    #draw_graph(G, 'Injection Rate {} Ejection Rate {} after {} hops.png'.format(injection_rate, ejection_rate, hops))
    degree_histogram(G, 'Degree Histogram after {} hops with Injection Rate {} and Ejection Rate {}.png'.format(hops, injection_rate, ejection_rate))

hops=500000
injection_rates=[.05]
ejection_rates=[.05]
for injection_rate in injection_rates:
    for ejection_rate in ejection_rates:
        main(init_graph())    
$\endgroup$
  • $\begingroup$ Can you explain how this is different from a Simple Symmetric Exclusion Process on a network? Is it that this tree is also evolving in time? The bit where you say that we now colour everything green is slightly misleading. $\endgroup$ – StatisticalMechanic Oct 19 '18 at 5:52
  • 1
    $\begingroup$ Yes, the whole network changes over time. Will clarify. $\endgroup$ – Salt Oct 19 '18 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.