Topics of Complex Social Networks:

Domination, Influence and Assortativity

By Moses Boudourides & Sergios Lenis

A. DOMINATING SETS

In [2]:
from IPython.display import Image
%matplotlib inline
In [3]:
%load_ext sage
In [4]:
#Experiment A1: COMPUTING DOMINATING SETS

from dom_set import domination,draw_doms,draw_domcomms
nodes = 40
p = 0.2
G=domination(nodes,p)
g=Graph(G)
dom=g.dominating_set()
idom=g.dominating_set(independent=True)
# print 'Edge list:',G.edges()
# print
print 'Minimum Dominating Set (red) = ',dom
print 'Independent Dominating Set (green) = ',idom
print

gamma=len(idom)
# print 'S(G) = ',dom
print 'Domination number = ',len(dom)
print 'Independent domination number = ',gamma
print
nodes=list(G.nodes())
dom_list=[]
node_set=set(nodes)
no_dom_list=[]
for i in G.nodes():
    node_set=set(nodes)
    nei=G.neighbors(i)
    nei.append(i)
    node_set=node_set-set(nei)
    G_Ni=G.subgraph(list(node_set))
    g_ni=Graph(G_Ni)
    dom_ni=g_ni.dominating_set(independent=False)
    if len(dom_ni)>=gamma:
        no_dom_list.append(i)
    else:
        dom_list.append(i)
print 'Possible Minimum Dominating Vertices (magenta) = ',dom_list
print 'Always Minimum Dominated Vertices (cyan) = ',no_dom_list

d=1
dd=3.5
draw_doms(G,dom,idom,dom_list,no_dom_list,d,dd)
Minimum Dominating Set (red) =  [4, 6, 10, 13, 14, 16]
Independent Dominating Set (green) =  [4, 8, 12, 23, 25, 26]

Domination number =  6
Independent domination number =  6

Possible Minimum Dominating Vertices (magenta) =  [3, 4, 5, 6, 8, 9, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 23, 25, 26, 27, 29, 30, 33, 34, 36, 38, 39]
Always Minimum Dominated Vertices (cyan) =  [0, 1, 2, 7, 10, 18, 22, 24, 28, 31, 32, 35, 37]
In [5]:
#Experiment A2: COMPUTING DOMINATING SETS AND COMMUNITIES
d=.8
dd=.8
c=1.2
cc=1.4
alpha=0.6
draw_domcomms(G,dom,idom,dom_list,no_dom_list,d,dd,c,cc,alpha)
# import community 
# par= community.best_partition(G)
# print par
# print max(par.values())
# print len(set(par.values()))
# from threeLayerCommunityParition import create_node_comm_graph, plot_graph

# broken_graph,broken_partition,npartition ,G= create_node_comm_graph(G,J.nodes(),FF.nodes(),DD.nodes())
# plot_graph(G,broken_graph,broken_partition,npartition,J.nodes(),FF.nodes(),DD.nodes(),d1=1.4,d2=5.,d3=0.8,withlabels=False,nodesize=100,layout=False)

B. NETWORK INFLUENCE AND SCALAR ATTRIBUTE ASSORTATIVITY

In [6]:
from influence import influence_sim,infdif_sim,polinfluence_sim
In [7]:
# Connected Erdos-Renyi random graph

nodes = 25
p = 0.2
iterations = 500
In [8]:
# Experiment B1: INFLUENCE 

# Susceptibility of all nodes (low)
sa = 0.1
influence_sim(nodes,p,sa,iterations)
In [9]:
# Experiment B2: INFLUENCE 

# Susceptibility of all nodes (high)
sa = 0.9
influence_sim(nodes,p,sa,iterations)
In [10]:
# Experiment B3: INFLUENCE 
# DIFFUSION BY INFLUENCE with heterogeneous susceptibilities

# Susceptibility of node 0 (the lowest)
sa = 0.
# Susceptibility of all other nodes (very low)
sb = 0.1
infdif_sim(nodes,p,sa,sb,iterations)
In [11]:
# Experiment B4: INFLUENCE 
# DIFFUSION BY INFLUENCE with heterogeneous susceptibilities

# Susceptibility of node 0 (low)
sa = 0.2
# Susceptibility of all other nodes (medium)
sb = 0.5
infdif_sim(nodes,p,sa,sb,iterations)
In [12]:
# Experiment B5: INFLUENCE 
# DIFFUSION BY INFLUENCE with heterogeneous susceptibilities

# Susceptibility of node 0 (medium)
sa = 0.4
# Susceptibility of all other nodes (low)
sb = 0.2
infdif_sim(nodes,p,sa,sb,iterations)
In [13]:
# Experiment B6: INFLUENCE 
# DIFFUSION BY INFLUENCE with heterogeneous susceptibilities

# Susceptibility of node 0 (high)
sa = 0.8
# Susceptibility of all other nodes (higher)
sb = 0.9
infdif_sim(nodes,p,sa,sb,iterations)
In [14]:
# Experiment B7: INFLUENCE 
# DIFFUSION BY INFLUENCE with heterogeneous susceptibilities

# Susceptibility of node 0 (high)
sa = 0.8
# Susceptibility of all other nodes (less high)
sb = 0.7
infdif_sim(nodes,p,sa,sb,iterations)
In [15]:
# Experiment B8: INFLUENCE 
# CONTRARIAN INFLUENCE 

# Susceptibility of all nodes (low)
sa = 0.1
polinfluence_sim(nodes,p,sa,iterations)
In [16]:
# Experiment B9: INFLUENCE 
# CONTRARIAN INFLUENCE 

# Susceptibility of all nodes (medium)
sa = 0.5
polinfluence_sim(nodes,p,sa,iterations)
In [17]:
# Experiment B10: INFLUENCE 
# CONTRARIAN INFLUENCE 

# Susceptibility of all nodes (high)
sa = 0.9
polinfluence_sim(nodes,p,sa,iterations)

C. MULTILAYER NETWORKS AND ENUMERATIVE ATTRIBUTE ASSORTATIVITY

In [18]:
# Experiment C1: A RANDOM BIPARTITE GRAPH

n=7
m=6
p=0.19

from bipartite_comm import *

G,layer1,layer2,layer3,slayer1,slayer2,edgeList,partition=create_3comms_bipartite(n,m,p)
pos,fig=plot_initial_bgraph(G)
create_colors_per_comm(G,layer1,layer2,layer3,slayer1,slayer2,pos,fig)

broken_graph,broken_partition,npartition ,fig= create_node_3attri_graph(G,layer1,layer2,layer3,slayer1,slayer2)
plot_graph_bip_3comms_2set(G,broken_graph,broken_partition,npartition,layer1,layer2,layer3,fig,d1=1.4,d2=5.,d3=0.8,withlabels=False,nodesize=100,layout=False)
broken_graph,broken_partition,npartition=create_node_2attri_graph(G,layer1,layer2,layer3,slayer1,slayer2)
plot_graph_bip_2set_3comms(G,broken_graph,broken_partition,npartition,slayer1,slayer2,layer3,fig,d1=1.4,d2=5.,d3=0.8,withlabels=False,nodesize=100,layout=False)
n = 5
m = 4
Number of edges = 8
Community1 =  [1, 3, 9]
Community2 =  [2, 10]
Community3 =  [4, 5, 7, 11]
In [27]:
# Experiment C2: A SYNTHETIC 3-LAYER RANDOM GRAPH IN THE TRIANGULAR TOPOLOGY

n1=n2=n3=50
p1=p2=p3=0.01
q1=q2=q3=0.01

from syntheticThreeLayerGraph import synthetic_three_level, plot_graph

G,J,FF,DD,edgeList = synthetic_three_level(n1,n2,n3,p1,p2,p3,q1,q2,q3,no_isolates=False)
pos=plot_graph(G,J,FF,DD,n1,n2,n3,d1=1,d2=10.,d3=0.8,nodesize=50,withlabels=False,edgelist=edgeList,layout=False,b_alpha=0.25)
In [20]:
from threeLayerCommunityParition import create_node_comm_graph, plot_graph

broken_graph,broken_partition,npartition ,G= create_node_comm_graph(G,J.nodes(),FF.nodes(),DD.nodes())
plot_graph(G,broken_graph,broken_partition,npartition,J.nodes(),FF.nodes(),DD.nodes(),d1=1.4,d2=5.,d3=0.8,withlabels=False,nodesize=100,layout=False)
In [21]:
# Experiment C3: AN ANALYTIC 3-LAYER RANDOM GRAPH IN THE 2-PATH TOPOLOGY

n = 150
p = 0.01
r1 = 0.333
r2 = 0.333
r3 = 0.333

from analyticThreeLayerGraph_l import analyticThreeLayerGraph, plot_graph

G, layer1, layer2, layer3, edgeList = analyticThreeLayerGraph(n,p,r1,r2,r3,G_isolates=True)
plot_graph(G,layer1,layer2,layer3,d1=3.5,d2=5.,d3=0.8,nodesize=100,withlabels=False,edgelist=edgeList,layout=False,alpha=0.2)
In [22]:
from threeLayerCommunityParition import create_node_comm_graph, plot_graph_stack

broken_graph,broken_partition,npartition,G = create_node_comm_graph(G,J.nodes(),FF.nodes(),DD.nodes())
plot_graph_stack(G,broken_graph,broken_partition,npartition,J.nodes(),FF.nodes(),DD.nodes(),d1=1.4,d2=5.,d3=0.8,withlabels=False,nodesize=100,layout=False)
In [23]:
# Experiment C4: A SYNTHETIC TEMPORAL RANDOM GRAPH WITH 3 SLICES

p1=p2=p3=0.1
n=50

from syntheticThreeLayerGraph_time import synthetic_three_level, plot_graph

G,J,FF,DD,JFD,edgeList = synthetic_three_level(n,p1,p2,p3,J_isolates=True,F_isolates=True,D_isolates=True)
created_pos=plot_graph(n,G,J,FF,DD,JFD,d1=2.,d2=3.,nodesize=50,withlabels=False,edgelist=edgeList,layout=False,b_alpha=0.05) #d=0.5 #d
In [24]:
from threeLayerCommunityParition import create_node_comm_graph, plot_graph_stack

broken_graph,broken_partition,npartition,G = create_node_comm_graph(G,J.nodes(),FF.nodes(),DD.nodes())
plot_graph_stack(G,broken_graph,broken_partition,npartition,J.nodes(),FF.nodes(),DD.nodes(),d1=1.4,d2=5.,d3=0.8,withlabels=False,nodesize=100,layout=False)
In [25]:
from threeLayer3AttributesPartition import create_node_3attri_graph, plot_graph_stack

r1=r2=r3=0.333

broken_graph,broken_partition,npartition,G = create_node_3attri_graph(G,J.nodes(),FF.nodes(),DD.nodes(),r1,r2,r3)
plot_graph_stack(G,broken_graph,broken_partition,npartition,J.nodes(),FF.nodes(),DD.nodes(),d1=1.4,d2=5.,d3=0.8,withlabels=False,nodesize=100,layout=False)
In [ ]: