{'fraction_non_alphanumeric': 0.03615375600609399, 'fraction_numerical': 0.009375366225243174, 'mean_word_length': 4.282265552460538, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Kirchhoff's Circuit Law Applications to Graph Simplification in Search Problems

This paper proposes a new analysis of graph using the concept of electric potential, and also proposes a graph simplification method based on this analysis. Suppose that each node in the weighted-graph has its respective potential value. Furthermore, suppose that the start and terminal nodes in graphs have maximum and zero potentials, respectively. When we let the level of each node be defined as the minimum number of edges/hops from the start node to the node, the proper potential of each level can be estimated based on geometric proportionality relationship. Based on the estimated potential for each level, we can re-design the graph for path-finding problems to be the electrical circuits, thus Kirchhoff's Circuit Law can be directed applicable for simplifying the graph for path-finding problems.


I. INTRODUCTION
The graph as a research topic is still held important positions in various fields, such as mathematics, theoretical computer science [1]- [6], networks, machine learning, and quantum computing [7]- [9]. In particular, many researchers in various fields are working for graph simplification because human beings are faced with complex graphs problems on many issues. Recently, various research topics related to graph simplification have been proposed in many areas. The summary of related research areas about graph simplification is as follows, i.e., data mining [10], decentralized composite optimization [11], network model simplification [12]- [16], biological network analysis [17], scheduling [18], and clustering coefficient [19]. As such, interest in graph simplification dramatically increases. Therefore, this paper proposes a novel graph simplification algorithm.
The graph simplification algorithm, which is introduced in this paper is based on graph analysis using electric potential. Our graph analysis method uses the concept of node level, this means the minimum number of edges from the start node to the node. By using the concept of levels and potentials, we create various transformed graphs and present a methodology for analyzing them with a geometric approach. The ultimate purpose of the methodology that we introduce is to estimate the entire voltage of the graph. By estimating the entire voltage of the graph and mapping the edge cost of the graph to the resistance, we can estimate the values of each current flowing through each edge using Kirchhoff's Circuit Law. Then, we can remove the edges, which have no current flow. This is an overview of the graph simplification algorithm.

II. BACKGROUND
In this section, we briefly describe two background concepts, i.e., electric potential and Kirchhoff's Circuit Law.

A. Electric Potential
The electric field E is a special vector function whose curl is always zero [20], [21] where the E can represent as the vector sum of each electric field produced by each charge as: where N can be a positive integer. Thus, the electric field E has following properties: According to Stokes' theorem [22], is satisfied by (2). By (3), following scalar function is defined: where o is a standard reference point, and r is a target point. The scalar function defined in (4) is called electric potential, and the differential form of (4) is as follows: In particular, in circuit theory, the difference of electric potential with these characteristics is called voltage.
• Kirchhoff's Current Law: KCL, also called Kirchhoff's first law, states that the sum of incoming currents at a junction is equal to the sum of outgoing currents at the junction. If we define the sign of incoming currents at the junction as positive and the sign of outgoing currents at the junction as negative, this law can be represented that the sum of the currents at each junction is zero as: where I n is each current n and x is the number of incoming or outgoing currents. In other words, KCL is the same as the law of conservation of charge.
• Kirchhoff's Voltage Law: KVL, also called Kirchhoff's second law, states that the sum of voltages of the closedcircuit loop is zero. If we define the sign of voltage similar to KCL's currents case, this law can be as: where V n is each voltage n and y is the number of voltages measured in the closed-circuit loop. In other words, KVL is the same as the law of energy conservation in a complete closed-circuit.

III. GRAPH ANALYSIS USING ELECTRIC POTENTIAL
This section describes the graph analysis method, which combines the concept of each electric potential to each node, before describing the graph simplification algorithm.

A. Motivation
Suppose that there is a graph G(v, e) in two-dimensional space where v and e represent nodes and edges, respectively. We have to search for a logically dependable path from the start to the terminal on G. We already know a variety of simple methods for searching paths, e.g., greedy algorithms [24], [25]. However, if the original graph G is too complex to find the logically dependable path in a simple way, it is essential to simplify the graph before searching for a logically dependable path, e.g., the shortest path, the minimum cost path, and so forth. Obviously, prior to simplifying the graph, we need to analyze the graph with various perspectives. As one of the new perspectives, we introduce the method of graph analysis using electric potential in the next section.

B. Graph Analysis using Electric Potential
We can interpret the graph as an electric circuit by regarding the electric resistances, junctions, and the voltage from the power supply as edges, nodes, and electric potential difference between the start and the terminal. If there is a voltage ε applied to the graph, then the start has an electric potential ε and the terminal has an electric potential 0. Then, eventually, the rests of the nodes (i.e., non-start and non-terminal nodes) have electric potentials between ε and 0.
Each junction in the electric circuit has its own electric potential, and no current flows through the resistance between the junctions with the same electric potential. In other words, if there are edges directly connected between nodes with the same electric potential in the graph, no current will flow through the edges. Thus, we may remove those edges in the graph. By removing the edges between equipotential nodes, Fig. 1. Sample graph G(7, 12). The yellow node S represents the start node and the red node T represents the terminal node. the complex graph can be simplified, and the simplified graph has an advantage in the path-finding problem.
To find equipotential nodes, the estimation of the electric potential of each node in the graph is required at first. The electric potential of each node can be estimated by finding each current value at each edge, and this value can be obtained from KCL and KVL. However, in order to use KCL and KVL, it is necessary to determine the voltage of the entire graph or the value of the currents diverging from the start. For these decisions, we introduce some concepts and analysis methods.
Level. The minimum number of edges between the start node to the target node.
In Fig. 1, the color represents the level of each node. Level 0, 1, 2, and 3 correspond to yellow, green, blue, and red, respectively. At the graph in Fig. 1, if we group the nodes at the same level, the graph transforms to level unit graph in Fig. 2. The number of edges in the transformed graph is equal to the number of edges in the original graph. The level unit transformed graph can be used in one process of the maximum voltage estimation in the graph simplification.
3-D Potential Graph. The 3-dimensional graph via mapping nodes' electric potential value to the height value.
Each node in a two-dimensional graph is simply represented by a circle or a point, but in a 3-D potential graph in Fig. 3, it can be represented by a node column. The representation of the node column's height indicating the electric potential can show visibly the presence of equipotential nodes. This graph is meaningful in itself but can be interpreted by transforming it as shown in Fig. 4. This transformation, aligning all the node  Fig. 1 can be transformed into this graph form. The height of each node column corresponds to each node's electric potential. Each level has a circular orbit, and each node column can be located only at the corresponding level orbit. columns in a straight line, has several analytical advantages. In Fig. 4, we can connect the highest point in the start node column where the edges first extend, the lowest point in the terminal node column where the edges finally gather, and the floor point of the start node column. These three points make a right triangle. Based on this right triangle, we can add some definitions to estimate the length of each side of the right triangle. And this allows us to determine the voltage of the entire graph.
Voltage Estimation. The entire voltage of the N -level graph can be estimated as a positive value less than the sum of the minimum costs between the level k − 1 and level k, where N and k are positive integers, 1 ≤ k ≤ N .
Before the description, suppose that there is an N -level graph, where N is a positive integer. Transform this graph in the form shown in Fig. 4, and then connect the highest point in the start node column, the lowest point in the terminal node column, and the floor point of the start node column to make a right triangle. The right triangle can be created as shown in Fig. 5. The entire voltage of the graph is equal to the electric potential of the level 0 node, which is equal to the length of SO. The straight line of each level represents each plane perpendicular to the plane where SOT is located. ST represents the shortest straight distance passing through the ideal nodes, that maybe existed or not. ST is shorter than any path, including the orange, red and green lines shown in  If we expressed the the edge costs between level k − 1 and level k as C (k−1),(k) , then the length of ST is as follows: where min means the minimum value. Since ST is the length of the longest side of SOT , the entire voltage corresponding to the length of SO should be smaller than ST . Thus, we can estimate the entire voltage of the graph as a positive value less than the sum of the minimum costs between adjacent levels. Definition 2. Let the ratio of the lengths between adjacent levels which divide OT be equal to the ratio of average costs between adjacent levels. The OT is the sum of the lengths between adjacent levels: where L (k−1),(k) is the lengths between level k − 1 and level k. We do not estimate the length of OT directly as a specific value, but we estimate the ratio of the lengths between adjacent levels that divide OT . The ratio of the lengths between adjacent levels is as follows: where avg means the average value. According to the similarity in geometry, this ratio is equal to the ratio of the lengths between adjacent ideal points which divide ST . Since we estimated the length of ST from (8), each appropriate length between adjacent ideal points also can be estimated with this ratio. This can be interpreted as an appropriate small edge costs between adjacent levels.

Algorithm 1 Graph Simplification
Volatage Estimation Input: G(v, e) Output: V max 1: Determine the level of each node in the given graph G. 2: Transform G to level unit graph G (v , e).

Edge Removal via Sub-current Estimation
Input: G(v, e), V max = x Output: G * (v, e ) 9: Map G to an electric circuit as C(e j ) → Resistance j . 10: Set the sub-currents of Resistance j as I j . 11: Create the system of linear equations using KCL and KVL. 12: Solve the system of linear equations and obtain I 1 · · · I j . 13: for int i = 1; i ≤ j; i++ do 14: if I i = 0 then 15: Remove e i on G. At the end of this section, we've shown the various transformations and interpretations of graphs through the concept of hypothetical electric potentials and also described hypothetical voltage estimation and appropriate edge cost estimation using two definitions. The related example is in Sec. IV-B.

IV. GRAPH SIMPLIFICATION USING KIRCHHOFF'S CIRCUIT LAW
This section describes the graph simplification algorithm based on the graph analysis and the voltage estimation of the entire graph, that are described in the previous section.

A. Proposed Algorithm
The algorithm consists of two processes, voltage estimation and edge removal via sub-current estimation.
A summary of the first process, voltage estimation, which described in the previous section as follows. At first, determine the level of each node in the given graph G(v, e), with |v| = i nodes and |e| = j edges, where i and j are positive integers. Construct a right triangle with three points: origin O = (0, 0, 0), start node S = (0, V max , 0), and terminal node T = (L, 0, 0), where V max and L are positive real numbers, and L < ST . Place ideal nodes of each level within ST in level order. In other words, as shown in Fig. 5, ideal nodes Fig. 6. Weighted-graph G (5,9). Each number next to each edge represents the edge cost (or weight).
should be placed sequentially on the diagonal of the right triangle. Calculate the estimated length of ST as shown in (8). Choose one of any positive real number smaller than the length of ST , and determined as V max . Normally, the value of V max is chosen from positive integer values.
The second process, edge removal via sub-current estimation, is performed as follows. Consider each edge costs (or weights) as each resistance, and consider V max , which is determined in the first process, as an entire voltage of graph. Set the sub-currents flowing at each edge of the graph as I 1 · · · I j , and create the system of linear equations using KCL and KVL. Solve the system of linear equations and find the values of the sub-currents I 1 · · · I j . To find the values of the sub-currents, the number of required linear equations is maximum j. Remove the edges with zero sub-currents.
This algorithm is effective when there are many equipotential nodes with no current flowing between them. In a complex graph, there is also a high probability of many equipotential nodes, so utilization is expected.

B. Case Study
In this section, we explain the graph simplification algorithm with a simple example.
(11) Fig. 7. Graph of sub-current applying KCL. The current flows from S with potential Vmax to T with potential zero.
Through the process 7 to 8 of Algorithm 1, V max can be a real number where 0 < V max < 4, i.e., we set V max = 3.
We consider each edge cost as each resistance and find the sub-current flowing through each edge. Fig. 7 shows the sub-currents flowing through each edge by applying KCL. Since there are 6 sub-currents in this graph, we may create the system of linear equations with 6 closed-circuit loops according to KVL are as follows: The values of sub-currents I 1 , I 2 , I 3 , I 4 , I 5 , and I 6 are obtained from (12) as 1, 1 2 , 1 3 , 1 2 , 0, and 1 3 , respectively. We confirm that there is no sub-current flowing through the edges ab and cb (i.e., I ab = I 2 − I 4 = 0 and I cb = I 5 = 0), so they will be removed. Fig 8 shows a simplified graph G * (5, 7) with two edges removal. In G * , there are only four paths from S to T , i.e., we can easily find the shortest path.
In addition, due to Definition 2, the ratio of the lengths between adjacent level which divides OT is obtained as: This ratio is equal to the ratio of the lengths between adjacent ideal points which divide ST , so SD and DT are as: where D is an ideal point of level 1 and ST = 4 is an obtained value from (11). SD and DT can be consider as relatively small edge costs between level 0 to 1 and level 1 to 2, respectively. In Fig. 6, the closest to SD = 1.185 among the edge costs between level 0 to 1 is 1 and the closest to DT = 2.815 among the edge costs between levels 1 to 2 is 3. These two edges correspond to the actual shortest path, represented by the orange path in Fig. 8. This is because, in this example, all the edges between the same level nodes are removed by the graph simplification algorithm.

V. CONCLUSIONS AND FUTURE WORK
In this paper, we have proposed graph analysis methods using electric potentials, such as level unit transformed graph analysis, straight-line alignment 3-D potential graph analysis, and geometric analysis. Based on these analysis methods, a graph simplification algorithm using Kirchhoff's Circuit Law has been proposed. The graph simplification algorithm consists of two processes, i.e., voltage estimation and edge removal via sub-current estimation. We have applied this algorithm to the example graph, and have demonstrated its usefulness as a preprocessing algorithm for path-finding problems. Thus, we also have confirmed the validity of the definitions underlying the proposed graph simplification algorithm.
As a future work direction, we will figure out which kinds of applications can be useful; and then conduct data-intensive performance evaluations.