<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Graph Generators
NetworkX comes with a large number of builtin graph generators. These can be especially useful for testing out new measures, metrics, and dynamics, on already well tested algorithms. In this notebook, we'll go through some of the different classes of graph generators included in NetworkX and write a few of our own. There are a lot of generators in NetworkX so before you implement your own check to see NetworkX already has it!
Step1:  Classic
NetworkX has the ability to make a bunch of the graphs we made in the previous section. They mainly fall under the classic namespace. For example, to make a complete graph, we could just use
Step2:  We don't actually have to use the full namespace call that is nx.generators.classic.complete_graph, everythin is under the nx module
Step3:  Exercises
Explore the classic generators, create graphs for at least 3 of them. You can list the graphs by typing nx.generators.classic.[TAB]. Read the documentation for each (remember you can type (nx.circulant_graph?) to see the documentation
Small Data Sets
NetworkX contains a number of small graphs from classic work. For example the Zachary karate Club is often used for testing community finding algorithms. It is included in networkx along with the community information
Step4:  Others are included under nx.generators.social. Explore the davis_southern_women_graph, what is special about it?
Step5:  Random Graphs
Random graphs are often used as models for various physical phenomena, and testing new measures and dynamics. NetworkX has a bunch of them built in. For example the classic Erdős–Rényi graph is implemented as gnp_random_graph which takes a number of nodes and a probability of connection between any two nodes
Step6:  A slight variant allows you to give it the total number of edges to be placed randomly
Step7:  Small World Graphs
The Erdős–Rényi does not have many of the properties seen in real world social network data, particularly, triadic closures. Watts and Strogatz developed a random graph model which accounts for this, and it's implemented in NetworkX!
Step8:  Power Law Random Graphs
A common feature of complex networks is their heavy-tailed degree distribution. That is the degrees of the nodes in a graph varies over many orders of magnitude. NetworkX contains a number of random graph models that have power law degree sequences. One of the most famous is the Barabási–Albert model. In this model nodes are added sequentially and a fixed number of edges between new nodes and existing nodes are added with nodes being selected with probability proportional to their degree.
Step9:  We'll plot degree sequences in the next lesson on graph analysis.
Excercise
One more exercise and then we'll get to the fun stuff. On disadvantage of the original Barabási–Albert model is that it had an integer average degree and the degree distribution was power law, but could only have integer exponent. Let's make a model that is able to ahve non-integer exponent.
Let's write a new model. Instead of adding a fixed number of edges with each node, we add a random number of edges from a Poisson distribution with mean $\lambda$. To ensure the graph stays connected, if the random number of edges is 0 we add at least 1 edge. Just as in the original model, we connect to new nodes to the graph to nodes proportional to the degree of the node.
First lets find a function that can generate poisson random numbers for us. It's easy to do with the numpy package, we can import numpy and then just call np.random.poisson to generate a random number with $Poisson(\lambda)$
Step10:  A trick to write a fast BA implementation is to maintain a list of nodes with nodes repeated in the list each time they have a connection made.
<ASSISTANT_TASK:>
Python Code:
import networkx as nx
Explanation: Graph Generators
NetworkX comes with a large number of builtin graph generators. These can be especially useful for testing out new measures, metrics, and dynamics, on already well tested algorithms. In this notebook, we'll go through some of the different classes of graph generators included in NetworkX and write a few of our own. There are a lot of generators in NetworkX so before you implement your own check to see NetworkX already has it!
End of explanation
C = nx.generators.classic.complete_graph(5)
C.edges()
Explanation: Classic
NetworkX has the ability to make a bunch of the graphs we made in the previous section. They mainly fall under the classic namespace. For example, to make a complete graph, we could just use:
End of explanation
C = nx.complete_graph(5)
Explanation: We don't actually have to use the full namespace call that is nx.generators.classic.complete_graph, everythin is under the nx module
End of explanation
KC = nx.karate_club_graph()
KC.nodes(data=True)
Explanation: Exercises
Explore the classic generators, create graphs for at least 3 of them. You can list the graphs by typing nx.generators.classic.[TAB]. Read the documentation for each (remember you can type (nx.circulant_graph?) to see the documentation
Small Data Sets
NetworkX contains a number of small graphs from classic work. For example the Zachary karate Club is often used for testing community finding algorithms. It is included in networkx along with the community information
End of explanation
DSW = nx.davis_southern_women_graph()
DSW.nodes()
Explanation: Others are included under nx.generators.social. Explore the davis_southern_women_graph, what is special about it?
End of explanation
ER = nx.gnp_random_graph(100,1.0/100)
ER.size()
Explanation: Random Graphs
Random graphs are often used as models for various physical phenomena, and testing new measures and dynamics. NetworkX has a bunch of them built in. For example the classic Erdős–Rényi graph is implemented as gnp_random_graph which takes a number of nodes and a probability of connection between any two nodes
End of explanation
ER2 =nx.gnm_random_graph(100,50)
ER2.size()
Explanation: A slight variant allows you to give it the total number of edges to be placed randomly
End of explanation
WS = nx.watts_strogatz_graph(10,4,.2)
WS.edges()
Explanation: Small World Graphs
The Erdős–Rényi does not have many of the properties seen in real world social network data, particularly, triadic closures. Watts and Strogatz developed a random graph model which accounts for this, and it's implemented in NetworkX!
End of explanation
BA = nx.barabasi_albert_graph(10000,1)
deg = BA.degree().values()
(min(deg),max(deg))
Explanation: Power Law Random Graphs
A common feature of complex networks is their heavy-tailed degree distribution. That is the degrees of the nodes in a graph varies over many orders of magnitude. NetworkX contains a number of random graph models that have power law degree sequences. One of the most famous is the Barabási–Albert model. In this model nodes are added sequentially and a fixed number of edges between new nodes and existing nodes are added with nodes being selected with probability proportional to their degree.
End of explanation
import numpy as np
np.random.poisson(3.2)
Explanation: We'll plot degree sequences in the next lesson on graph analysis.
Excercise
One more exercise and then we'll get to the fun stuff. On disadvantage of the original Barabási–Albert model is that it had an integer average degree and the degree distribution was power law, but could only have integer exponent. Let's make a model that is able to ahve non-integer exponent.
Let's write a new model. Instead of adding a fixed number of edges with each node, we add a random number of edges from a Poisson distribution with mean $\lambda$. To ensure the graph stays connected, if the random number of edges is 0 we add at least 1 edge. Just as in the original model, we connect to new nodes to the graph to nodes proportional to the degree of the node.
First lets find a function that can generate poisson random numbers for us. It's easy to do with the numpy package, we can import numpy and then just call np.random.poisson to generate a random number with $Poisson(\lambda)$
End of explanation
def poisson_BA(n,l):
    start = max(2,np.random.poisson(l)) # start with at least two nodes
    
    G = nx.complete_graph(start)
    
    #an easy list to grab nodes from
    repeated_nodes = []
    # For each node at it's label to the list for as many times as it's degree
        
    u = start
    while u < n:
        # Using the the poisson random number generator, generate a number of connections
        # Make Sure it's greater than 1
        # Store that variable in `connections`
        for _ in range(connections):
            # For as many connections as it has select a node at random from repeated_nodes
            # Hint numpy as a np.random.choice function
            # Be sure to update repeated_nodes!
        u += 1
    return G
        
G = poisson_BA(1000,np.pi)
deg = G.degree().values()
min(deg),max(deg)
np.mean(G.degree().values())
Explanation: A trick to write a fast BA implementation is to maintain a list of nodes with nodes repeated in the list each time they have a connection made.
End of explanation
<END_TASK>