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)