Skip to content

Getting Started with Graph

Source: Graph Machine Learning

A graph (simple undirected graph) is defined as a couple , where is a set of nodes (or vertices) and is a collection of two-elements sets, or edge (also called links), representing connection between two nodes that are part of the set . Theres in no order between edge in Elements of , and represent the same edge. Some basic definitions:

  • The order is the number of vertex
  • The size is the number of edges
  • The degree of a vertex is the count of edges that connect to it

  • Neighbor of a Vertex: The neighbors of a vertex, v, in a graph are all the vertices that share an edge with v. In other words, if there is a direct connection from v to another vertex, that vertex is considered a neighbor.

  • Neighborhood Graph: The neighborhood graph of a vertex, v, in a graph is the subgraph induced by the neighborhood of v. This includes the vertex v itself and all of its neighbors. It also includes all edges that connect these vertices.

  • Induced Subgraph: An induced subgraph is a subset of a graph that consists of a set of vertices and all of the edges connecting pairs of vertices within that set. If you have a graph G and you choose a subset of its vertices to form a new graph H, then H is an induced subgraph of G if for any two vertices in H, they are adjacent (connected by an edge) in H if and only if they are adjacent in G.

So while every neighborhood graph is an induced subgraph (since it's formed from a subset of vertices and the edges between them), not every induced subgraph is a neighborhood graph (since it could be formed from any arbitrary subset of vertices, not necessarily all neighbors of a given vertex).

import networkx as nx
G = nx.Graph()
V = {'Dublin', 'Paris', 'Milan', 'Rome'}
E = [('Milan', 'Dublin'), ('Milan', 'Paris'), ('Paris', 'Dublin'), ('Milan', 'Rome')]
G.add_nodes_from(V)
G.add_edges_from(E)
nx.draw_networkx(G)
print(f"The nodes or vertices of graph G:\nV = {G.nodes}")
print(f"The edges of graph G:\nE = {G.edges}")
print(f"Graph order: {G.number_of_nodes()}")
print(f"Graph size: {G.number_of_edges()}")
print(f"Degree for nodes: { {v: G.degree(v) for v in G.nodes} }")
print(f"Neigbors for nodes: { {v: list(G.neighbors(v)) for v in G.nodes} }")
ego_graph_milan = nx.ego_graph(G, "Milan")
print(f"Nodes: {ego_graph_milan.nodes}")
print(f"Edges: {ego_graph_milan.edges}")
nx.draw_networkx(ego_graph_milan)

Ego graph is another term of neighborhood graph.

# Add new nodes and edges
new_nodes = {'London', 'Madrid'}
new_edges = [('London', 'Rome'), ('Madrid', 'Paris')]
G.add_nodes_from(new_nodes)
G.add_edges_from(new_edges)
print(f"V = {G.nodes}")
print(f"E = {G.edges}")
nx.draw_networkx(G)
‌
‌
‌