<jupyter_start><jupyter_text>SD212: Graph mining Lab 2: Random graphsYou will learn to generate random graphs. You **must** be connected to Telecom ParisTech network!  Getting started<jupyter_code>from connector import Connector
import warnings
import itertools 
base_url = 'http://172.16.17.32:8234'
lab_id = 'lab2'<jupyter_output><empty_output><jupyter_text>To do* Enter your login and test it using question 0<jupyter_code># Enter your login (family name + first letter of first name)
login = 'zhuf'
connector = Connector(base_url, lab_id, login)
get_question = connector.get_question
post_answer = connector.post_answer
post_text = connector.post_text
get_question(0)<jupyter_output><empty_output><jupyter_text>Import<jupyter_code>import networkx as nx<jupyter_output><empty_output><jupyter_text>The documentation is available [here](https://networkx.readthedocs.io/en/stable/).<jupyter_code>%pylab notebook
import numpy as np<jupyter_output><empty_output><jupyter_text>1. Erdos-Renyi graphs The `networkx` package contains functions to generate random graphs.<jupyter_code>n = 100
p = 0.03
G = nx.erdos_renyi_graph(n,p)
print(nx.info(G))


def show_random(n,p):
    G = nx.erdos_renyi_graph(n, p)
    figure()
    nx.draw(G, node_size = 3)
    print(nx.info(G))
nx.draw(G, node_size=3)<jupyter_output><empty_output><jupyter_text>To do* Generate several instances of the graph and observe the results* Answer question 1 **(1 point)****Hint:** Use the local approximation of the graph by a Galton-Watson tree.<jupyter_code>show_random(100,0.01)
arg = get_question(1)
print(arg)
# to be modified
answer = arg['p'] ** 200
answer
post_answer(1, answer)<jupyter_output>Wrong answer<jupyter_text>We now focus on the largest connected component of the graph.<jupyter_code>n = 200
p = 0.01
G = nx.erdos_renyi_graph(n,p)
Gc = max(nx.connected_component_subgraphs(G), key = len)
print(nx.info(Gc))<jupyter_output>Name: 
Type: Graph
Number of nodes: 168
Number of edges: 191
Average degree:   2.2738<jupyter_text>To do* Generate several instances of the graph (for different values of $n$ and $p$) and observe the size and the average degree of the largest connected component* Answer question 2 **(open answer)**<jupyter_code>get_question(2)
post_text(2)<jupyter_output><empty_output><jupyter_text>2. Preferential attachment The degree distribution of an Erdos-Renyi graph is approximately binomial (for large n), as shown below.<jupyter_code>n = 500
p = 0.01
G = nx.erdos_renyi_graph(n,p)
degree_list = [G.degree(u) for u in G.nodes()]
figure() 
hist(degree_list)
xlabel('Degree')
ylabel('Number of nodes')
show()<jupyter_output><empty_output><jupyter_text>The Barabasi-Albert model, based on the principle of **preferential attachment**, provides a random graph with a **power-law** degree distribution.<jupyter_code>n = 100
d = 3 # degree of new nodes
G = nx.barabasi_albert_graph(n, d) 
G.add_edges_from(nx.complete_graph(d).edges()) # adding the initial clique (removed by networkx)
print(nx.info(G))
degree_list = [G.degree(u) for u in G.nodes()]
figure() 
hist(degree_list)
xlabel('Degree')
ylabel('Number of nodes')
show()<jupyter_output><empty_output><jupyter_text>To do* Code a function that generates a Barabasi-Albert graph starting from any initial graph (not necessarily a clique)* Answer question 3 **(1.5 points)**<jupyter_code>def general_barabasi_albert_graph(n, d, init_G):
    print(init_G.edges)
    # init_G must be connected with at least d and at most n nodes
    G = init_G.copy()
    nb_new_node = n - G.number_of_nodes()
    if nb_new_node == 0: return
    for nb in range(G.number_of_nodes(), n):
        p_list = np.array([y for x,y in G.degree()])
        p_list = p_list / np.sum(p_list)
        selected_nodes = np.random.choice(list(G.nodes), size=d,replace=False, p=p_list)
        for node in selected_nodes:
            G.add_edge(nb, node)
        # to be completed
        # you may use the function nb.random.choice
    return G    
p_list = [x for x in G.degree()]
print(G.degree)
# To check
G = general_barabasi_albert_graph(100, 3, nx.complete_graph(3))
print(nx.info(G))
arg = get_question(3)
init_G = nx.Graph(arg['edge_list'])
G  = general_barabasi_albert_graph(100, 3, init_G)
post_answer(3, list(G.edges()))<jupyter_output>This is correct!<jupyter_text>3. Configuration model We now focus on graphs with some given degree sequence. The Havel-Hakimi algorithm generates such a graph provided the degree sequence is valid (that is, **graphical**); otherwise, it returns an error. The resulting graph is not necessarily connected.<jupyter_code>H = nx.havel_hakimi_graph([3,2,3,2])
figure()
nx.draw(H)<jupyter_output><empty_output><jupyter_text>To do * Test various degree sequences (you may get valid sequences from actual graphs, see the [networkx graph generators](https://networkx.github.io/documentation/networkx-1.10/reference/generators.html))* Download the graph of [Les Miserables](http://perso.telecom-paristech.fr/~bonald/graphs/lab2.zip) (co-occurence of characters in chapters of the novel of Victor Hugo)* Answer questions 4 and 5 **(0.5 point each)**<jupyter_code>G = nx.read_graphml("miserables.graphml", node_type = int)
print(nx.info(G))
names = nx.get_node_attributes(G, 'name')
figure()
nx.draw(G, labels = names, node_size=3)
get_question(4)
def solve4(G):
    degrees = dict(G.degree).values()
    H = nx.havel_hakimi_graph(degrees)
    return nx.number_connected_components(H),H
answer,H = solve4(G)
post_answer(4, answer)
get_question(5)
inGH = nx.intersection(G,H)
answer = inGH.number_of_edges()
post_answer(5, answer)<jupyter_output>This is correct!<jupyter_text>The configuration model generates a random  instance of a **multi-graph** with some given  degree sequence. Any sequence of even sum is valid. Self-loops and multi-edges must be removed to get a simple graph.<jupyter_code>C = nx.configuration_model([2,4])
print(nx.info(C))
C = nx.Graph(C)
C.remove_edges_from(C.selfloop_edges())
print(nx.info(C))<jupyter_output>Name: 
Type: Graph
Number of nodes: 2
Number of edges: 1
Average degree:   1.0000<jupyter_text>To do* Test various degree sequences* Generate random configurations associated with the degree sequence of Les Miserables and observe the fraction of common edges with the original graph* Answer questions 6 **(0.5 point)** and 7 **(open answer)**<jupyter_code>get_question(6)
254 * 254 *2 / (77 * 76)
post_answer(6, 22.049)
get_question(7)
post_text(7)<jupyter_output><empty_output><jupyter_text>4. Stochastic block model The stochastic block model generates graphs with some underlying structure in blocks.<jupyter_code>block_sizes = [10, 20, 30]
G = nx.random_partition_graph(sizes = block_sizes, p_in = 0.4, p_out = 0.02)
figure()
pos = nx.spring_layout(G)
nx.draw(G, pos, node_size=3)
block_indices = cumsum(block_sizes)
nodes = nx.draw_networkx_nodes(G, pos, nodelist = range(block_indices[0]), node_color = 'r', node_size=3)
nodes = nx.draw_networkx_nodes(G, pos, nodelist = range(block_indices[0], block_indices[1]), node_color = 'b', node_size=3)
nodes = nx.draw_networkx_nodes(G, pos, nodelist = range(block_indices[1], block_indices[2]), node_color = 'g', node_size = 3)<jupyter_output><empty_output><jupyter_text>To do* Code a function that generates a stochastic block model with any block connectivity matrix (see below)* Answer question 8 **(1 point)**<jupyter_code>block_connectivity_matrix = np.array([[0.5,0.02,0.01],[0.02,0.4,0.],[0.01,0.,0.3]])
block_connectivity_matrix
# Probability of an edge between a node in block 0 and a node in block 1
block_connectivity_matrix[0,1]
block_sizes = [10, 20, 30]
G = nx.Graph()
for i in range(len(block_sizes)):
    G = nx.disjoint_union(block_sizes[i], block_connectivity_matrix[i][i])
print(nx.connected_components(G))



def stochastic_block_model(block_sizes, block_connectivity_matrix):
    G = nx.Graph()
    subgraphs = []
    intervals = [0]
    for ind in range(len(block_sizes)):
        G = nx.disjoint_union(G, nx.erdos_renyi_graph(block_sizes[ind], block_connectivity_matrix[ind, ind])) # merge the subgraphs
    print(G.c
       
    # Now connect the inter block nodes:
    for interblocks in itertools.combinations(range(len(block_sizes)), 2):
        for i in range(intervals[interblocks[0]], intervals[interblocks[0]+1]):
            for j in range(intervals[interblocks[1]], intervals[interblocks[1]+1]):
                if np.random.uniform() < block_connectivity_matrix[interblocks[0], interblocks[1]]:
                    G.add_edge(i,j)
    return G

arg = get_question(8)
print(arg)
block_sizes = arg['block_sizes']
block_connectivity_matrix = np.array(arg['block_connectivity_matrix'])
G = stochastic_block_model(block_sizes, block_connectivity_matrix)
post_answer(8, list(G.edges()))<jupyter_output>(TIME EXPIRED) Wrong answer
{'fraction_non_alphanumeric': 0.11800818553888132, 'fraction_numerical': 0.023419736243747158, 'mean_word_length': 5.6795747911921035, 'pattern_counts': {'":': 0, '<': 64, '<?xml version=': 0, '>': 63, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '17', 'dir': 'jupyter-structured-clean-dedup', 'id': '560402', 'license': 'Apache-2.0', 'n_tokens_mistral': 3195, 'n_tokens_neox': 3037, 'n_words': 805, 'path': 'SD212/lab_session/lab2.ipynb', 'repo_name': 'zhufangda/Telecom-Paristech', 'size': '8798'}