Network Characteristics

代码：

################################################################################
# CS 224W (Fall 2019) - HW1
# Starter code for Question 1
# Last Updated: Sep 25, 2019
################################################################################
import snap
import numpy as np
import matplotlib.pyplot as plt
import random
# Setup
erdosRenyi = None
smallWorld = None
collabNet = None
# Problem 1.1
def genErdosRenyi(N=5242, E=14484):
    """
    :param - N: number of nodes
    :param - E: number of edges
    return type: snap.PUNGraph
    return: Erdos-Renyi graph with N nodes and E edges
    """
    ############################################################################
    # TODO: Your code here!
    Graph = snap.TUNGraph().New()
    for i in range(N):
        Graph.AddNode(i + 1)
    for i in range(E):
        a, b = random.randint(1, N), random.randint(1, N)
        while a == b:
            a, b = random.randint(1, N), random.randint(1, N)
        Graph.AddEdge(a, b)
    ############################################################################
    return Graph
def genCircle(N=5242):
    """
    :param - N: number of nodes
    return type: snap.PUNGraph
    return: Circle graph with N nodes and N edges. Imagine the nodes form a
        circle and each node is connected to its two direct neighbors.
    """
    ############################################################################
    # TODO: Your code here!
    # Graph = snap.TUNGraph()
    Graph = snap.TUNGraph().New()
    for i in range(N):
        Graph.AddNode(i + 1)
    ############################################################################
    return Graph
def connectNbrOfNbr(Graph, N=5242):
    """
    :param - Graph: snap.PUNGraph object representing a circle graph on N nodes
    :param - N: number of nodes
    return type: snap.PUNGraph
    return: Graph object with additional N edges added by connecting each node
        to the neighbors of its neighbors
    """
    ############################################################################
    # TODO: Your code here!
    for i in range(N - 2):
        if not i:
            Graph.AddEdge(i + 1, N)
            Graph.AddEdge(i + 1, N - 1)
            Graph.AddEdge(i + 2, N)
            Graph.AddEdge(N - 1, N)
        Graph.AddEdge(i + 1, i + 2)
        Graph.AddEdge(i + 1, i + 3)
    ############################################################################
    return Graph
def connectRandomNodes(Graph, M=4000):
    """
    :param - Graph: snap.PUNGraph object representing an undirected graph
    :param - M: number of edges to be added
    return type: snap.PUNGraph
    return: Graph object with additional M edges added by connecting M randomly
        selected pairs of nodes not already connected.
    """
    ############################################################################
    # TODO: Your code here!
    for i in range(M):
        a, b = random.randint(1, Graph.GetNodes()), random.randint(1, Graph.GetNodes())
        while a == b or Graph.IsEdge(a, b):
            a, b = random.randint(1, Graph.GetNodes()), random.randint(1, Graph.GetNodes())
        Graph.AddEdge(a, b)
    ############################################################################
    return Graph
def genSmallWorld(N=5242, E=14484):
    """
    :param - N: number of nodes
    :param - E: number of edges
    return type: snap.PUNGraph
    return: Small-World graph with N nodes and E edges
    """
    Graph = genCircle(N)
    Graph = connectNbrOfNbr(Graph, N)
    Graph = connectRandomNodes(Graph, 4000)
    return Graph
def loadCollabNet(path):
    """
    :param - path: path to edge list file
    return type: snap.PUNGraph
    return: Graph loaded from edge list at `path and self edges removed
    Do not forget to remove the self edges!
    """
    ############################################################################
    # TODO: Your code here!
    Graph = snap.LoadEdgeList(snap.TUNGraph, path)
    for edge in Graph.Edges():
        if edge.GetSrcNId() == edge.GetDstNId:
            Graph.DelEdge(edge.GetSrcNId(), edge.GetDstNId)
    ############################################################################
    return Graph
def getDataPointsToPlot(Graph):
    """
    :param - Graph: snap.PUNGraph object representing an undirected graph
    return values:
    X: list of degrees
    Y: list of frequencies: Y[i] = fraction of nodes with degree X[i]
    """
    ############################################################################
    # TODO: Your code here!
    X, Y = [], []
    map = {}
    for node in Graph.Nodes():
        out_deg = node.GetOutDeg()
        if out_deg not in map:
            map[out_deg] = 1
        else:
            map[out_deg] += 1
    X = [item for item in map.keys()]
    X.sort()
    Y = [map[x] for x in X]
    ############################################################################
    return X, Y
def Q1_1():
    """
    Code for HW1 Q1.1
    """
    global erdosRenyi, smallWorld, collabNet
    erdosRenyi = genErdosRenyi(5242, 14484)
    smallWorld = genSmallWorld(5242, 14484)
    collabNet = loadCollabNet("ca-GrQc.txt")
    x_erdosRenyi, y_erdosRenyi = getDataPointsToPlot(erdosRenyi)
    plt.loglog(x_erdosRenyi, y_erdosRenyi, color='y', label='Erdos Renyi Network')
    x_smallWorld, y_smallWorld = getDataPointsToPlot(smallWorld)
    plt.loglog(x_smallWorld, y_smallWorld, linestyle='dashed', color='r', label='Small World Network')
    x_collabNet, y_collabNet = getDataPointsToPlot(collabNet)
    plt.loglog(x_collabNet, y_collabNet, linestyle='dotted', color='b', label='Collaboration Network')
    plt.xlabel('Node Degree (log)')
    plt.ylabel('Proportion of Nodes with a Given Degree (log)')
    plt.title('Degree Distribution of Erdos Renyi, Small World, and Collaboration Networks')
    plt.legend()
    plt.show()
# Execute code for Q1.1
Q1_1()
# Problem 1.2 - Clustering Coefficient
def calcClusteringCoefficientSingleNode(Node, Graph):
    """
    :param - Node: node from snap.PUNGraph object. Graph.Nodes() will give an
                   iterable of nodes in a graph
    :param - Graph: snap.PUNGraph object representing an undirected graph
    return type: float
    returns: local clustering coeffient of Node
    """
    ############################################################################
    # TODO: Your code here!
    C = 0.0
    k = Node.GetOutDeg()
    if k == 0 or k == 1:
        return C
    neighbours = []
    for i in range(k):
        neighbours.append(Node.GetOutNId(i))
    exc = 0
    degs = 0
    for node in neighbours:
        deg = Graph.GetNI(node).GetOutDeg()
        degs += deg
        for i in range(deg):
            if Graph.GetNI(node).GetOutNId(i) not in neighbours:
                exc += 1
    e = (degs - exc) / 2
    C = float(2 * e) / float(k * (k - 1))
    ############################################################################
    return C
def calcClusteringCoefficient(Graph):
    """
    :param - Graph: snap.PUNGraph object representing an undirected graph
    return type: float
    returns: clustering coeffient of Graph
    """
    ############################################################################
    # TODO: Your code here! If you filled out calcClusteringCoefficientSingleNode,
    #       you'll probably want to call it in a loop here
    C = 0.0
    for node in Graph.Nodes():
        C += calcClusteringCoefficientSingleNode(node, Graph)
    C /= float(Graph.GetNodes())
    ############################################################################
    return C
def Q1_2():
    """
    Code for Q1.2
    """
    C_erdosRenyi = calcClusteringCoefficient(erdosRenyi)
    C_smallWorld = calcClusteringCoefficient(smallWorld)
    C_collabNet = calcClusteringCoefficient(collabNet)
    print('Clustering Coefficient for Erdos Renyi Network: %f' % C_erdosRenyi)
    print('Clustering Coefficient for Small World Network: %f' % C_smallWorld)
    print('Clustering Coefficient for Collaboration Network: %f' % C_collabNet)
# Execute code for Q1.2
Q1_2()

结果：
我画出来是这样的，不知道对不对：

Clustering Coefficient for Erdos Renyi Network: 0.001620
Clustering Coefficient for Small World Network: 0.283908
Clustering Coefficient for Collaboration Network: 0.532029

Structural Roles: Rolx and ReFex

数据集：hw1-q2.zip

代码：

import snap
import numpy as np
import matplotlib.pyplot as plt
def take_first(item):
    return item[0]
def basic_features(j):
    G = snap.TUNGraph.Load(snap.TFIn("hw1-q2.graph"))
    x = calculate_basic_feature(G, j)
    similarity = []
    for i in range(G.GetMxNId() - 1):
        if i + 1 == j:
            continue
        y = calculate_basic_feature(G, i + 1)
        if not np.linalg.norm(x) or not np.linalg.norm(y):
            sim = 0
        else:
            sim = np.dot(x, y) / (np.linalg.norm(x) * np.linalg.norm(y))
        similarity.append((sim, i + 1))
    similarity.sort(key=take_first, reverse=True)
    print(similarity[0], similarity[1], similarity[2])
def calculate_basic_feature(graph, nid):
    node = graph.GetNI(nid)
    degree = node.GetOutDeg()
    neighbours = []
    for i in range(degree):
        neighbours.append(node.GetOutNId(i))
    exc = 0
    degs = 0
    for id in neighbours:
        deg = graph.GetNI(id).GetOutDeg()
        degs += deg
        for i in range(deg):
            if graph.GetNI(id).GetOutNId(i) not in neighbours:
                exc += 1
    edges = float(degs - exc) / 2.0 + degree
    return np.array([degree, edges, exc]).astype(np.float64)
def generate_initial_matrix(G):
    matrix = np.array([])
    for i in range(G.GetMxNId() - 1):
        x = calculate_basic_feature(G, i + 1)
        matrix = np.append(matrix, x)
    return matrix.reshape(G.GetMxNId() - 1, -1)
def recursive_features(G, features):
    matrix = np.array([])
    length = features.shape[1]
    for i in range(G.GetMxNId() - 1):
        sum = np.zeros(length)
        node = G.GetNI(i + 1)
        for i in range(node.GetOutDeg()):
            sum += features[node.GetOutNId(i) - 1]
        if not node.GetOutDeg():
            mean = np.zeros(length)
        else:
            mean = sum / float(node.GetOutDeg())
        new_feature = np.concatenate([mean, sum])
        matrix = np.append(matrix, new_feature)
    matrix = matrix.reshape(G.GetMxNId() - 1, -1)
    matrix = np.append(features, matrix, axis=1)
    return matrix
def top_5(features, k):
    size = features.shape[0]
    similarity = []
    x = features[k - 1]
    for i in range(size):
        if i == k - 1:
            continue
        y = features[i]
        if not np.linalg.norm(x) or not np.linalg.norm(y):
            sim = 0
        else:
            sim = np.dot(x, y) / (np.linalg.norm(x) * np.linalg.norm(y))
        similarity.append((sim, i + 1))
    similarity.sort(key=take_first, reverse=True)
    for i in range(5):
        print(similarity[i])
    plot_role(similarity)
def plot_role(similarity):
    similarity = [item[0] for item in similarity]
    plt.hist(similarity, bins=100)
    plt.xlabel('cosine similarity with node 9')
    plt.ylabel('number of nodes')
    plt.title('role discovery')
    plt.show()
if __name__ == '__main__':
    # basic_features(9)
    G = snap.TUNGraph.Load(snap.TFIn("hw1-q2.graph"))
    feature = generate_initial_matrix(G)
    feature = recursive_features(G, feature)
    feature = recursive_features(G, feature)
    top_5(feature, 9)

结果：
还是不知道对不对

(0.9996996545960188, 415) (0.9985681322700889, 496) (0.9985681322700888, 16)
(0.9979737326427643, 973)
(0.99665936768074, 415)
(0.9944804316381064, 537)
(0.9942402370209513, 496)
(0.9934389028651474, 24)

机器学习

Project1

Network Characteristics

Structural Roles: Rolx and ReFex