Graph Embedding

1. networkx库介绍

<! -- more -->

1.1 图数据结构

import networkx as nx
G = nx.Graph()

这里定义的图G是一组节点（顶点）和已经识别的节点对（边）的集合。节点可以是任意的可哈希的对象，例如文本字符串、图像等。图的初始化的源码解析如下：

"""Initialize a graph with edges, name, or graph attributes.

        Parameters
        ----------
        incoming_graph_data : input graph (optional, default: None)
            Data to initialize graph. If None (default) an empty
            graph is created.  The data can be an edge list, or any
            NetworkX graph object.  If the corresponding optional Python
            packages are installed the data can also be a NumPy matrix
            or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph.

        attr : keyword arguments, optional (default= no attributes)
            Attributes to add to graph as key=value pairs.

        See Also
        --------
        convert

        Examples
        --------
        >>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
        >>> G = nx.Graph(name='my graph')
        >>> e = [(1, 2), (2, 3), (3, 4)]  # list of edges
        >>> G = nx.Graph(e)

        Arbitrary graph attribute pairs (key=value) may be assigned

        >>> G = nx.Graph(e, day="Friday")
        >>> G.graph
        {'day': 'Friday'}

        """

1.2 从文件中导入图数据

一般使用最多的函数是read_edgelist,作用是从一个边的集合中来获取一幅图

def read_edgelist(path, comments="#", delimiter=None, create_using=None,
                  nodetype=None, data=True, edgetype=None, encoding='utf-8'):
    """Read a graph from a list of edges.

    Parameters
    ----------
    path : file or string
       File or filename to read. If a file is provided, it must be
       opened in 'rb' mode.
       Filenames ending in .gz or .bz2 will be uncompressed.
    comments : string, optional
       The character used to indicate the start of a comment.
    delimiter : string, optional
       The string used to separate values.  The default is whitespace.
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
       Graph type to create. If graph instance, then cleared before populated.
    nodetype : int, float, str, Python type, optional
       Convert node data from strings to specified type
    data : bool or list of (label,type) tuples
       Tuples specifying dictionary key names and types for edge data
    edgetype : int, float, str, Python type, optional OBSOLETE
       Convert edge data from strings to specified type and use as 'weight'
    encoding: string, optional
       Specify which encoding to use when reading file.

    Returns
    -------
    G : graph
       A networkx Graph or other type specified with create_using

    Examples
    --------
    >>> nx.write_edgelist(nx.path_graph(4), "test.edgelist")
    >>> G=nx.read_edgelist("test.edgelist")

    >>> fh=open("test.edgelist", 'rb')
    >>> G=nx.read_edgelist(fh)
    >>> fh.close()

    >>> G=nx.read_edgelist("test.edgelist", nodetype=int)
    >>> G=nx.read_edgelist("test.edgelist",create_using=nx.DiGraph)

    Edgelist with data in a list:

    >>> textline = '1 2 3'
    >>> fh = open('test.edgelist','w')
    >>> d = fh.write(textline)
    >>> fh.close()
    >>> G = nx.read_edgelist('test.edgelist', nodetype=int, data=(('weight',float),))
    >>> list(G)
    [1, 2]
    >>> list(G.edges(data=True))
    [(1, 2, {'weight': 3.0})]

    See parse_edgelist() for more examples of formatting.

    See Also
    --------
    parse_edgelist
    write_edgelist

    Notes
    -----
    Since nodes must be hashable, the function nodetype must return hashable
    types (e.g. int, float, str, frozenset - or tuples of those, etc.)
    """

'''以下是调用'''
self.G = nx.read_edgelist(filename,create_using=nx.DiGraph,nodetype=int)

2. 网络嵌入方法实现

2.1 deepwalk

随机游走突出一个字随机，以下是该模型的主要算法。

def get_sequence(self, start_node) -> List[int]:
    '''
    ->用于类型提醒，返回的是列表
    对单个节点进行随机游走算法
    :param start_node:
    :return: 一条随机游走序列
    '''
    walk = [start_node]#放的是节点的id
    '''在邻居中取walk_length的节点，少了的话就取所有'''
    while len(walk) < self.walk_length:
        current_node = walk[-1]
        neighbors = list(self.g.neighbors(current_node))
        if len(neighbors) > 0:
            walk.append(random.choice(neighbors))
        else:
            break
    return walk

def random_walk(self) -> List[List[int]]:
    '''
    随机游走算法，采集图中点的序列，超参数walk_length,window_size,大规模图可以并行优化
    :return: 二维list，随机游走生成的序列
    '''
    walks = []#存放的是整个随机游走序列
    for walk_iter in range(self.num_walks):
        print("当前游走次数：{}".format(walk_iter + 1))
        node_list = list(self.g.nodes())
        random.shuffle(node_list)#随机打乱节点
        for node in node_list:
            walks.append(self.get_sequence(node))
    return walks

def train(self):
    t = time.time()
    print("开始随机游走")
    sentence = self.random_walk()
    corpus = []
    #将sentence转换为str类型
    for idx, each in enumerate(sentence):
        corpus.append(list(map(str, sentence[idx])))
    print("随机游走结束，开始训练！")
    word2vec = Word2Vec(
        sentences=corpus,
        vector_size=self.dim,
        window=self.window_size,
        min_count=0,
        workers=0,
        sg=1
    )

    for node in self.g.nodes():
        self.vectors[node] = word2vec.wv[str(node)]

    print("模型训练完成！算法总共消耗时间：{}秒".format(round(time.time() - t, 3)))

2.2 node2vec

赏

谢谢你请我吃糖果