🥭C++和Python通信引文道路社评电商大规模行为图结构数据模型

关键词

C++ | Python | 图论 | 统计 | 图算法 | 节点 | 度 | 算法 | 数学 | 概率 | 分布 | 距离 | 最短路径 | 聚类系数 | 遍历节点 | 通信 | 引文 | 社交 | 社区 | 协作论文 | 电商 | 计算机 | 边缘 | 道路 | 图表 | 社评 | 时间 | 在线 | 用户 | 面对面 | 图分类 | 电信 | 点评 | 影响力

C++和Python通信引文道路社评电商大规模行为图结构数据模型 | Notion亚图跨际 on Notion

🏈指点迷津 | Brief

🎯要点

1. 🎯图论数学逻辑和计算：🖊定向网络节点和边 | 🖊节点的入度 | 🖊出度和度 | 🖊源节点 | 🖊汇节点 | 🖊 孤立节点 | 🖊入度分布和出度分布 | 🖊平均度 | 🖊平均入读和平均出度 | 🖊随机节点距离 | 🖊最短路径长度分布 | 🖊节点聚类系数及分布和平均聚类系数。

2. 🎯图结构和算法：🖊计算入度和出度分布并绘制每个分布的幂律 | 🖊广度优先搜索算法遍历节点 | 🖊绘制算法遍历节点的累积分布 | 🖊创建前向后向度优先搜索算法图 | 🖊计算出入分量的节点 | 🖊计算两节点存在的路径的概率 | 🖊计算两网络弱连通分量算法下，连接的节点对概率。

3. 🎯图模型和概率：🖊生成埃尔多什-雷尼随机图 | 🖊生成配置模型随机图 | 🖊计算上述图度分布 | 🖊计算最短路径长度分布 | 🖊聚类系数分布 | 🖊弱连通分量算法大小分布。

4. 🎯小世界图 | 🎯社交软件图结构 | 🎯点评网络 | 🎯影响力

🍇Python图节点和度

数学和计算机科学中的“图” 由“节点”（也称为“顶点”）组成。节点之间可能连接也可能不连接。

节点“a”与节点“c”连接，但“a”不与“b”连接。 两个节点之间的连接线称为边。 如果节点之间的边是无向的，则该图称为无向图。 如果一条边从一个顶点（节点）指向另一个顶点（节点），则图称为有向图。 有向边称为弧。 尽管图表看起来非常理论化，但许多实际问题都可以用图表来表示。 它们通常用于对物理、生物学、心理学，尤其是计算机科学中的问题或情况进行建模。 在计算机科学中，图用于表示通信网络、数据组织、计算设备、计算流程、在后一种情况下，它们用于表示数据组织，例如操作系统的文件系统或通信网络。 网站的链接结构也可以看作是图，即有向图，因为链接是有向边或弧。 Python 没有内置的图形数据类型或类，但在 Python 中很容易实现它们。 一种数据类型非常适合在 Python 中表示图形，即字典。 我们图中的图表可以通过以下方式实现：

 graph = { "a" : {"c"},
           "b" : {"c", "e"},
           "c" : {"a", "b", "d", "e"},
           "d" : {"c"},
           "e" : {"c", "b"},
           "f" : {}
         }

上面字典的键是我们图的节点。 相应的值是用节点设置的，节点通过边连接。 集合比列表或元组更好，因为这样，两个节点之间只能有一条边。 没有比这更简单、更优雅的方式来表示图表了。边也可以理想地实现为具有两个元素（即端节点）的集合。这对于无向图来说是理想的。对于有向图，我们更喜欢使用列表或元组来实现边。

生成所有边列表的函数：

 def generate_edges(graph):
     edges = []
     for node in graph:
         for neighbour in graph[node]:
             edges.append({node, neighbour})
 ​
     return edges
 ​
 print(generate_edges(graph))

输出：

 [{'c', 'a'}, {'c', 'b'}, {'b', 'e'}, {'c', 'd'}, {'c', 'b'}, {'c', 'e'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]

正如我们所看到的，没有包含节点“f”的边。 “f”是我们图中的一个孤立节点。以下 Python 函数计算给定图的孤立节点：

 def find_isolated_nodes(graph):
     isolated = set()
     for node in graph:
         if not graph[node]:
             isolated.add(node)
     return isolated

如果您查看我们类的以下清单，您可以在 init 方法中看到我们使用字典“self._graph_dict”来存储顶点及其相应的相邻顶点。

 class Graph(object):
 ​
     def __init__(self, graph_dict=None):
 ​
         if graph_dict == None:
             graph_dict = {}
         self._graph_dict = graph_dict
 ​
     def edges(self, vertice):
 ​
         return self._graph_dict[vertice]
         
     def all_vertices(self):
 ​
         return set(self._graph_dict.keys())
 ​
     def all_edges(self):
   
         return self.__generate_edges()
 ​
     def add_vertex(self, vertex):
 ​
         if vertex not in self._graph_dict:
             self._graph_dict[vertex] = []
 ​
     def add_edge(self, edge):
 ​
         edge = set(edge)
         vertex1, vertex2 = tuple(edge)
         for x, y in [(vertex1, vertex2), (vertex2, vertex1)]:
             if x in self._graph_dict:
                 self._graph_dict[x].add(y)
             else:
                 self._graph_dict[x] = [y]
 ​
     def __generate_edges(self):
 ​
         edges = []
         for vertex in self._graph_dict:
             for neighbour in self._graph_dict[vertex]:
                 if {neighbour, vertex} not in edges:
                     edges.append({vertex, neighbour})
         return edges
     
     def __iter__(self):
         self._iter_obj = iter(self._graph_dict)
         return self._iter_obj
     
     def __next__(self):
         return next(self._iter_obj)
 ​
     def __str__(self):
         res = "vertices: "
         for k in self._graph_dict:
             res += str(k) + " "
         res += "\nedges: "
         for edge in self.__generate_edges():
             res += str(edge) + " "
         return res

我们想玩一下我们的图表。我们从迭代图表开始。迭代意味着迭代顶点。

 g = { "a" : {"d"},
       "b" : {"c"},
       "c" : {"b", "c", "d", "e"},
       "d" : {"a", "c"},
       "e" : {"c"},
       "f" : {}
     }
 ​
 graph = Graph(g)
 ​
 for vertice in graph:
     print(f"Edges of vertice {vertice}: ", graph.edges(vertice))

输出：

 Edges of vertice a:  {'d'}
 Edges of vertice b:  {'c'}
 Edges of vertice c:  {'c', 'd', 'b', 'e'}
 Edges of vertice d:  {'c', 'a'}
 Edges of vertice e:  {'c'}
 Edges of vertice f:  {}