Chromatic and Community Partitions of Networks

Moses Boudourides & Sergios Lenis

This notebook is executed by "sage -ipython notebook." The following are the libraries that need to be loaded first.

In [29]:
from IPython.display import Image
%matplotlib inline
%load_ext sage
%load_ext autoreload
import networkx as nx
import matplotlib.pyplot as plt
import matplotlib
import random
from sage.graphs.graph_coloring import vertex_coloring
The sage extension is already loaded. To reload it, use:
  %reload_ext sage
The autoreload extension is already loaded. To reload it, use:
  %reload_ext autoreload

Generating a connected E-R random graph G

In [30]:
%autoreload 2
from chAs import create_conn_random_graph_chrom,create_conn_random_graph,draw_domcomms

nodes=30
p=0.15

G=create_conn_random_graph(nodes,p)
g=Graph(G)
vc=vertex_coloring(g, value_only=False)

print 'An example of a connected E-R random graph with n =', nodes, 'and p =', "%.2f" % p
print
print 'G is connected:', nx.is_connected(G)
print 'Number of vertices of G:', len(G.nodes())
print 'Number of edges of G:', len(G.edges())
print 'List of edges of random graph G:'
print G.edges()
# print vc
An example of a connected E-R random graph with n = 30 and p = 0.15

G is connected: True
Number of vertices of G: 30
Number of edges of G: 68
List of edges of random graph G:
[(0, 17), (0, 26), (1, 4), (1, 5), (1, 8), (1, 10), (1, 16), (1, 21), (1, 24), (1, 26), (1, 28), (2, 8), (2, 24), (2, 13), (2, 22), (3, 5), (3, 6), (3, 8), (3, 9), (3, 10), (3, 12), (3, 23), (3, 27), (3, 29), (4, 24), (4, 29), (4, 9), (5, 24), (5, 12), (6, 10), (6, 28), (6, 29), (7, 8), (7, 12), (7, 16), (7, 18), (7, 19), (7, 27), (8, 15), (8, 17), (8, 22), (8, 24), (9, 10), (9, 11), (9, 14), (9, 24), (9, 29), (10, 23), (11, 20), (11, 21), (11, 25), (12, 19), (12, 24), (13, 24), (13, 28), (13, 14), (14, 25), (14, 28), (14, 21), (16, 28), (18, 25), (18, 29), (19, 26), (19, 27), (20, 23), (24, 28), (25, 26), (28, 29)]

Computing the chromatic and community partitions of G

In [31]:
%autoreload 2
from chAs import create_conn_random_graph_chrom,draw_domcomms,modul_arity
import community as comm

cn=vertex_coloring(g, value_only=True)
collpar={}
for v,i in enumerate(vc):
    for j in i:
        collpar[j]=v
part=comm.best_partition(G) 
print 'Chromatic number of G =',cn
print 'Chromatic partition of G:'
print vc
print 'Chromatic modularity of G =', "%.4f" % modul_arity(G,'vertex_colors')
print
print 'Community number of G =', max(part.values())+1
for nd in G.nodes():
    G.add_node(nd,vertex_colors=collpar[nd],comm_coll=part[nd])
print 'Community partition of G:'
parLis=[]
partdi={}
for i,k in part.items():
    if k not in partdi:
        partdi[k]=[i]
    else:
        partdi[k].append(i)
for i,k in partdi.items():
    parLis.append(k)
print parLis
for i,v in enumerate(parLis):
    gg=Graph(G.subgraph(v))
    print 'Community %i (as a subgraph) has chromatic number %i' %(i,vertex_coloring(gg, value_only=True))
print 'Community modularity of G =', "%.4f" % comm.modularity(part,G)

d=.8
dd=.8
c=1.2
cc=1.4
alpha=0.2
ealpha=.2
vcc={}
for i,nd in enumerate(vc):
    for ndd in nd:
        vcc[ndd]=i
        
draw_domcomms(G,G.nodes(),[],[],[] ,vcc,part,d,dd,c,cc,alpha,ealpha)
Chromatic number of G = 4
Chromatic partition of G:
[[1, 3, 13, 19, 11, 22, 18, 17, 15], [4, 10, 28, 5, 8, 25, 27, 21, 20, 0], [24, 29, 14, 7, 26, 23], [6, 9, 12, 2, 16]]
Chromatic modularity of G = 0.0000

Community number of G = 5
Community partition of G:
[[0, 11, 17, 18, 20, 25, 26], [1, 14, 16, 21, 28], [2, 8, 13, 15, 22, 24], [3, 4, 6, 9, 10, 23, 29], [5, 7, 12, 19, 27]]
Community 0 (as a subgraph) has chromatic number 2
Community 1 (as a subgraph) has chromatic number 3
Community 2 (as a subgraph) has chromatic number 3
Community 3 (as a subgraph) has chromatic number 3
Community 4 (as a subgraph) has chromatic number 3
Community modularity of G = 0.3489

Chromatic and Community Partitions of 2-Layer Graphs:

The Lazega 2-Layer Network of Researchers and Institutions in French Cancer Studies

In [21]:
import pickle
import networkx as nx
lg = pickle.load(open('lazega_graph.txt'))
# print nx.info(lg)
G = nx.Graph(lg)
# print nx.info(G)
# print G.nodes()
nodes = G.nodes()
nodes.sort()
# print nodes
# print len(nodes)
llist=[]
xlist=[]
for i in nodes:
    if 'l' in i:
        llist.append(i)
    if 'x' in i:
        xlist.append(i)
# print llist
# print xlist
# print len(llist)
# print len(xlist)
names = llist+xlist
# print names
# print len(names)
idies = range(208)
mapping_dict={}
for i in range(len(names)):
    mapping_dict[names[i]] = idies[i]
# print mapping_dict
nx.relabel_nodes(G, mapping_dict, copy=False)
# print G.nodes()
Out[21]:
<networkx.classes.graph.Graph object at 0x7fa1b86fee50>
In [22]:
%autoreload 2

from chAs import plot_paral
layer1=range(82)
layer2=range(82,208)
# d1=0.6 #1.5
# d2=15. # 5.
# d3=0.3 #0.8
nodesize=200
withlabels=False
edgelist=[]
layout=True
alpha=0.25
plot_paral(G,layer1,layer2,d1=1.,d2=11.,d3=.8,d4=.5,d5=.5,d6=7,nodesize=50,withlabels=True,edgelist=[],layout=True,alpha=0.5)

Taking the connected components of both upper and lower layers

In [23]:
F=nx.Graph(G)
print nx.isolates(F)
F.remove_nodes_from(nx.isolates(F))
layer1=range(82)
fl1=nx.subgraph(F,layer1)
F.remove_nodes_from(nx.isolates(fl1))
fl1.remove_nodes_from(nx.isolates(fl1))
# fl1=nx.subgraph(F,layer1)
print nx.is_connected(fl1)
layer2=range(82,208)
fl2=nx.subgraph(F,layer2)
F.remove_nodes_from(nx.isolates(fl2))
fl2.remove_nodes_from(nx.isolates(fl2))
print nx.is_connected(fl2)
layer1=fl1.nodes()
layer2=fl2.nodes()
print
print "INSTITUTIONS (UPPER LAYER) ARE DENOTED AS SQUARES"
print
print layer1
print
print "RESEARCHERS (LOWER LAYER) ARE DENOTED AS CIRCLES"
print
print layer2
# d1=0.6 #1.5
# d2=15. # 5.
# d3=0.3 #0.8
# print type(F)
nodesize=200
withlabels=False
edgelist=[]
layout=True
alpha=0.25
plot_paral(F,layer1,layer2,d1=1.,d2=9.,d3=.8,d4=1.,d5=.5,d6=11,nodesize=200,withlabels=True,edgelist=[],layout=True,alpha=0.5)
[]
True
True

INSTITUTIONS (UPPER LAYER) ARE DENOTED AS SQUARES

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 59, 60, 61, 62, 63, 64, 65, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 80, 81]

RESEARCHERS (LOWER LAYER) ARE DENOTED AS CIRCLES

[82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207]