## 4 The Proposed Model
### BFS-Based Candidate Set Generation Strategy  
The BFS-based candidate set generation strategy can effectively search the induced subgraph space containing query position \(q\). The strategy mainly contains the following four important ideas:  
1. Search the induced subgraph space containing query position \(q\) in ascending order of the number of vertices. In particular, the first layer of the induced subgraph space is the query position self-constructed induced subgraph \(\{\{q\},\emptyset,l\}\). Its importance will be explained in detail later. 2. Divide all the vertices of the data graph into two subsets. The two subsets are defined as follows: \(V^{in}\) denotes the vertices already contained in the current induced subgraph. Note that it must have query position \(q\in V^{in}\). \(V^{out}\) denotes the vertices not contained in the current subgraph. Note that it must have \(V^{out}=V-V^{in}\). 3. When performing BFS for the \((i+1)\)-th layer induced subgraph from the \(i\)-th layer induced graph (containing \(i\) vertices), select a vertex \(v\) from the subset \(V^{out}\) of the \(i\)-th layer induced subgraph. If vertex \(v\) is connected to any vertex of the subgraph, then add vertex \(v\) into the vertex set of the subgraph to generate a new induced subgraph (containing \(i+1\) vertices). 4. We eliminate the generated duplicate induced subgraphs, which have been already obtained by other \(i\)-th layer induced subgraphs and vertices in \(V^{out}\), which can greatly reduce subsequent computational overhead. Figure 6 is an example of the induced subgraph space search path. Data graph \(G=(V,E,I)\), \(V=\{v_{1},v_{2},v_{3},v_{4},v_{5}\}\), \(E=\{(v_{1},v_{2}),(v_{1},v_{3}),(v_{1},v_{5}),(v_{2},v_{4}),(v_{2},v_{5}),(v_ {3},v_{4}),(v_{4},v_{5})\}\). Set query position \(q=v_{2}\). \(g_{3}\) is an induced subgraph of graph \(G\) with three vertices and containing the query position \(q\). \(g_{3}=(V_{3},E_{3},l)\), \(V^{in}_{3}=V_{3}=\{v_{1},v_{2},v_{4}\}\), \(V^{out}_{3}=V-V^{in}_{3}=\{v_{3},v_{5}\}\) in this example. Select a vertex \(v_{5}\) from \(V^{out}_{3}\) and find the existence of edge \((v_{1},v_{5})\) between vertex \(v_{5}\) and vertex \(v_{1}\) in \(V^{in}_{3}\) after checking. Then, add the vertex \(v_{5}\), the edge \((v_{1},v_{5})\) and other edges between \(v_{5}\) and other vertices in \(V^{in}_{3}\) (\((v_{2},v_{5})\) and \((v_{4},v_{5})\) in this example) to the induced subgraph \(g_{3}\). In this case, we can get the induced subgraph \(g_{4}\) with four vertices and containing the query position \(q\). Similarly, select the vertex \(v_{3}\) from \(V^{out}_{3}\) and obtain another induced subgraph \(g^{\prime}_{4}\). Algorithm 2 shows the entire process of the BFS-based candidate set generation algorithm. \(G_{i}\) denotes a set of the induced subgraphs with \(i\) vertices, and \(g_{i}\) denotes an induced subgraph with \(i\) vertices, thus \(g_{i}\in G_{i}\). Algorithm initialization is extremely important in the algorithm. The induced subgraph composed of the query position \(q\) is initialized as the first layer induced subgraph, i.e., \(g_{1}=\{\{q\},\emptyset,l\}\), \(G_{1}=g_{1}\) in Line 1. This initialization can ensure that the subgraphs searched by the algorithm absolutely contain query position \(q\) and that all other induced subgraphs not containing query position \(q\) are prune off, which makes the candidate set non-repetitive and complete. Then, we search the space from the second layer to the \(|V|\)-th layer (Line 2). The details to generate a candidate have been already introduced above and are shown in Lines 3\(\sim\)9. If \(g_{i}\) does not exist in \(G_{i}\), add \(g_{i}\) to \(G_{i}\) (Lines 10\(\sim\)12). In addition, it is worth mentioning that there is no need to find all the induced subgraphs containing the query position \(q\). When the MUIS\((q)\) that satisfies the condition is obtained in a certain layer, the search can be stopped. Figure 6: An example of the induced subgraph space search path.