Comment
Author: Admin | 2025-04-28
A set of edges. Example of a graph is shown in Fig. 1. A graph G is an ordered pair (V, E) consisting of a set of vertices V = {v1, v2, v3, v4, v5} and V is connected to each other by and a set of edges E = {e1, e2, e3, e4}. A label function, L, maps a vertex or an edge to a label. Figure 1: Example of graph G. Assume subgraph G ’(V’, E’) is a subgraph of the graph G (V, E), where edges and vertices are subsets of E and V respectively. Figure 2 shows examples of subgraphs such that S1, S2, and S3 are subgraphs of G of Fig. 1. Figure 2: Subgraphs of graph G. Subgraph isomorphism: Given two undirected graphs G and H. There is an isomorphism between G and H, if there is a bijection f between their vertices (f: V(G) →V(H)), Hence, two vertices u, v are adjacent to each other in G if and only if f (u), f (v) are adjacent in H. These two graphs are topologically identical. In Fig. 3, the subgraph g1 isisomorphic to the subgraph (u3, u4, u5), where (u3, u4, u5) is a subgraph of the input graph G. This is also called an embedding g1 in graph in G. Figure 3: Example of graph inputs as a series of small graphs. Static graph: A graph G = (V, E) consists of a set of nodes V, and a set of edges E ⊆ V ×V, where V and E do not change over time. Dynamic graph (evolving graph): An evolving graph GD = (VD, ED) consists of a set of nodes VD, and a set of edges ED ⊆ VD × VD. GD is changed by node additions or deletions, edge additions or deletions over time. Figure 3 shows an example of a dynamic graph at three points of time (t1, t2 and t3). At time t2, there is a deletion of the edge u7−u8. At time t3, edge u7−u8 andedge u3−u10are added. Increments for dynamic graphs In the context of dynamic graphs, graph increments can be represented as (a) a series of small graphs, or (b) a stream of node and edge updates (Ray, Holder & Choudhury, 2014). Increments as a stream of nodes and edges: In this kind of dynamic graphs, the increments consist of nodes and edges that
Add Comment