I have a particular type of dynamical graph in mind which I'll describe below to provide motivation for my question, but I think the question applies to anyone working with graphs that change over time.
Motivation
I've recently started experimenting with particular type of dynamical graph: Starting with a random digraph (loops ok, no parallel edges), we'll pick a node, say $A$, at random and perform a random move (with the caveat that if a move would create an edge that already exists, it isn't allowed). The moves are:
- Tail move: $C \leftarrow A \rightarrow B \implies A \rightarrow B \rightarrow C$
The name comes from imagining the tail of the edge $(A,C)$ following the edge $(A,B)$. $(A,C)$ is deleted and $(B,C)$ is created. - Head move: $A \rightarrow B \rightarrow C \implies A \rightarrow C \leftarrow B$
Here, the head of edge $(A,B)$ follows the edge $(B,C)$. $(A,B)$ is deleted and $(A,C)$ is created. - Spin move: $A \rightarrow B \implies A \leftarrow B$
And finally we can just "spin" the arrow around to point the other way. $(A,B)$ is deleted and $(B,A)$ is created.
Note our moves preserve number of edges and connectivity. If one imagines some node on our digraph with an in-degree much larger than the average, then there's a sense in which this node is "attractive" i.e., it will be more likely to have heads and tails move to it. Even if the node has both a large in-degree and out-degree, it will accumulate tails and heads faster than it can get rid of them on average (I think). Curious about this phenomenon, I wrote a program (in python) that generates a random digraph and performs a large number of random moves and draws the resulting graph along with some typical measures. I include the code for completeness:
"""
Created on Wed Dec 27 06:28:38 2017
@author: Salt
"""
import networkx as nx
from networkx.drawing.nx_agraph import graphviz_layout
import matplotlib.pyplot as plt
from random import choice
def tmove(G, source, target1, target2): #Tail move
G.remove_edge(source, target2)
G.add_edge(target1, target2)
def hmove(G, source, target1, target2): #Head move
G.remove_edge(source, target1)
G.add_edge(source, target2)
def spin(G, source, target):
G.remove_edge(source, target)
G.add_edge(target, source)
def list_tmoves(G, node): #Return a list of all possible tail moves for node
neighbors=list(G.neighbors(node))
tmove_list=[]
for s in neighbors:
for w in neighbors:
if w==s:
continue
if not G.has_edge(s,w):
tmove_list.append([tmove, s, w])
return tmove_list
def list_hmoves(G, node): #Return a list of all possible head moves for node
neighbors=list(G.neighbors(node))
hmove_list=[]
for t in neighbors:
neighbors_neighbors=list(G.neighbors(t))
for u in neighbors_neighbors:
if not G.has_edge(node, u):
hmove_list.append([hmove, t, u])
return hmove_list
def list_smoves(G, node): #Return a list of all possible spin moves for node
neighbors=list(G.neighbors(node))
smove_list=[]
for v in neighbors:
if not G.has_edge(v, node):
smove_list.append([spin, v])
return smove_list
def list_moves(G, node): #Generate and return all available moves for a node as a list.
move_list=[]
move_list.extend(list_tmoves(G, node))
move_list.extend(list_hmoves(G, node))
move_list.extend(list_smoves(G, node))
return move_list
def draw_graph(G, filename):
out_degrees=[G.out_degree(node) for node in G.nodes()] #Color nodes by out-degree. blue -> yellow
in_degrees=[(G.in_degree(node)+1)*5 for node in G.nodes()] #Size nodes by in-degree.
nx.draw(G, pos=graphviz_layout(G, 'sfdp'), node_color=out_degrees, node_size=in_degrees, cmap=plt.get_cmap('plasma'))
plt.savefig(filename)
plt.show()
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)))
plt.hist(out_degrees, bins, alpha=0.5, color = 'blue')
plt.hist(in_degrees, bins, alpha=0.5, color = 'green')
plt.title("Degree Histogram: In = Green, Out = Blue")
plt.savefig(filename)
plt.show()
def print_info(G):
H=G.to_undirected()
print("Order is", G.number_of_nodes(), "and size is", G.number_of_edges())
print("Degree assortativity is", nx.degree_assortativity_coefficient(G))
print("(Undirected)Average shortest path length is", nx.average_shortest_path_length(H))
print("(Undirected)Average clustering is", nx.average_clustering(H))
print("(Undirected)Largest clique size is", nx.graph_clique_number(H))
number_of_nodes=1000
edge_probability=.003
G=nx.gnp_random_graph(number_of_nodes,edge_probability, None, True)
while not nx.is_connected(G.to_undirected()): #Try again if not connected
G=nx.gnp_random_graph(number_of_nodes,edge_probability, None, True)
draw_graph(G, 'Random Graph Order {} Size {}.png'.format(G.number_of_nodes(), G.number_of_edges()))
degree_histogram(G,'Random Graph Degree Histogram Order {} Size {}.png'.format(G.number_of_nodes(), G.number_of_edges()))
print_info(G)
move_number = 100000
for i in range(move_number):
random_node=choice(list(G.nodes()))
move_list=list_moves(G, random_node)
while len(move_list)==0: #To avoid incrementing i when random_node has no available moves
random_node=choice(list(G.nodes()))
move_list= list_moves(G, random_node)
random_move=choice(move_list)
random_move[0](G, random_node, *random_move[1:])
"""
random_move[0] is one of the functions: tmove, hmove, spin.
*random_move[1:] are the rest of parameters needed to call random_move[0]
"""
draw_graph(G,'Random Graph Order {} Size {} after {} moves.png'.format(G.number_of_nodes(), G.number_of_edges(), move_number))
degree_histogram(G, 'Random Graph Degree Histogram Order {} Size {} after {} moves.png'.format(G.number_of_nodes(), G.number_of_edges(), move_number))
print_info(G)
Sample output of program:
Random graph with 1000 nodes and edge probability .003
Order is 1000 and size is 2994
Degree assortativity is -0.00508606504995
(Undirected)Average shortest path length is 4.067115115115115
(Undirected)Average clustering is 0.006344624819624813
(Undirected)Largest clique size is 3
Graph after 100000 moves
Order is 1000 and size is 2994
Degree assortativity is -0.03387504717
(Undirected)Average shortest path length is 3.9654994994994994
(Undirected)Average clustering is 0.007967397298264166
(Undirected)Largest clique size is 3
This is typical output in that the graph tends to be drawn more compact, but "hairier".
So does this model expand or contract on average(starting from a random digraph) i.e., does the average shortest (undirected) path length increase? (Tests have been inconclusive, but seem to depend on density of edges.) What's the attractor (if it exists)? What are the more interesting measures of dynamical random graphs? Can I tell if anything interesting is happening?
An aside (for anyone interested in Combinatorial Game Theory): An interesting game can be played by starting from a star-graph with all edges pointing away from the center and alternating moves with a friend (allowing only Tail moves and Head moves). Normal game rules apply (if it's your turn and you have no moves, you lose). We note that the game will end with a star-graph with all edges pointing toward the center. If you only allow Tail moves, however, the game will end with a path graph. (These are impartial games, and if you can tell me what nimber each starting configuration is equal to, I'll mail you a cookie.)