Identify Critical Nodes in Complex Network with Large Language Models

## Abstract

Abstract Identifying critical nodes in networks is a classical decision-making task, and many methods struggle to strike a balance between adaptability and utility. Therefore, we propose an approach that empowers Evolutionary Algorithm (EA) with Large Language Models (LLMs), to generate a function called "score_nodes" which can further be used to identify crucial nodes based on their assigned scores.
Our model consists of three main components: Manual Initialization, Population Management, and LLMs-based Evolution. It evolves from initial populations with a set of designed node scoring functions created manually. LLMs leverage their strong contextual understanding and rich programming skills to perform crossover and mutation operations on the individuals, generating excellent new functions. These functions are then categorized, ranked, and eliminated to ensure the stable development of the populations while preserving diversity.
Extensive experiments demonstrate the excellent performance of our method, showcasing its strong generalization ability compared to other state-of-the-art algorithms. It can consistently and orderly generate diverse and efficient node scoring functions. All source codes and models that can reproduce all results in this work are publicly available at this link: https://anonymous.4open.science/r/LLM4CN-6520

## 1 Introduction

Various networks widely exist in the real world, such as social networks, biological networks, etc .
For the network, identifying an optimal set of critical nodes for which the activation/removal has the maximized impact is a basic research problem with broad applications in epidemic control, influence maximization, etc ; .
From the perspective of combinational optimization, this problem could be considered as a kind of optimal search task, in which the computational complexity increases exponentially along with the size of the network .
Existing approaches to this problem can be categorized as follows: from heuristic methods to optimization-based methods, and finally, to learning-based methods.

The first kind of work is the basic methods based on heuristics, such as using the Degree Centrality , to judge whether the node is critical or not, which is simple yet very effective and efficient, showing superior performance in many kinds of networks  ; .
The second kind of work further tries to re-formulate the problem with approximated optimization problems.
Some other algorithms like CoreHD and WeakNeighbors utilize k-core decomposition, in which the k-core of a network is defined as the maximal subgraph with every node having a degree of at least $k$. These methods progressively eliminate nodes with the highest degrees within their respective k-cores to identify key nodes.
Furthermore, Min-Sum focuses on creating an acyclic network by removing nodes that form loops, followed by utilizing greedy tree-breaking algorithms to decompose the remaining forest into smaller disconnected components.
Another work, GND , adopts a spectral approach to iteratively partition the network into two components.
These methods have the advantage of fast computation, but they may lead to sub-optimal solutions, or even lack a suitable solution altogether.
Recently, with the advancement of deep learning, some works ; approach the problem by using neural networks to learn the node importance or ranking nodes adaptively. That is, they utilize neural networks to assign scores to network nodes, determining their importance based on these scores.

Despite these advances, there still exists a key challenge of adaptability-utility dilemma, which largely affects the real application values of these methods.
Specifically, the heuristic or optimization methods provide the same solution for all kinds of networks, but however, ignoring the different characteristics, which leads to poor performance in those unpopular networks.
The learning-based methods try to search the critical nodes adaptively, but are faced with high search costs in such a huge search space, which in turn, leads to poor utility.

Recently, Large Language Models (LLMs) have shown a human-like ability in many tasks, from basic natural language processing, to code generation, and some high-level logical reasoning and decision-making tasks ; ; .
Inspired by these advances, we propose a novel solution that adopts LLMs to generate the solution and design an evolutional learning framework to fully unleash LLMs.
Specifically, we utilize LLMs-empowered evolutionary algorithms to address the critical node problem, with LLMs performing crossover and mutation operations, continuously iterating to generate new solutions.

The contributions of this work can be summarized as follows:

- •
We approach the fundamental problem of critical node detection from a brand new perspective of LLMs, for which the original problem is transformed into a code-generation task.
- •
We propose a general framework integrating LLMs and evolutional learning. We propose a generation-updation mechanism for LLMs and the crossover-mutation method for evolutional learning.
- •
We conduct extensive experiments on both real-world and synthetic networks, and the results show the superior performance of our proposed method. The searched solutions can further inspire researchers and practitioners in this area.

## 2 Problem Statement

In this work, our objective is to learn a function $f$ that can identify critical nodes within a network.

Given a network $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ represents the set of nodes $\{v_{1},v_{2},...,v_{V}\}$ and $\mathcal{E}$ represents the set of edges $\{e_{1},e_{2},...,e_{E}\}$, we aim to identify a set of critical nodes $\mathcal{V}_{c}$ = $\{v_{c_{1}},v_{c_{1}},...,v_{c_{L}}\}$, such that when these nodes are removed or attacked, the network experiences significant disruptions.
For the sake of facilitating function reading, we represent the network $\mathcal{G}$ as an adjacency matrix $\mathbf{A}=\{0,1\}^{V\times V}$, where $\mathbf{A}_{jk}=1$ indicates that there is an edge between node $v_{j}$ and node $v_{k}$; otherwise, $\mathbf{A}_{jk}=0$.

Many existing methods rely on a crucial parameter, which is the number of target nodes $N$, directly impacting the algorithm’s performance.
In order to ensure the efficiency and generalization of the function learned by our approach, our objective function $f$ does not include the variable $N$.
Instead, it will take the network’s adjacency matrix $\mathbf{A}$ as input and produce scores for each node $\mathcal{S}=\{s_{v_{1}},s_{v_{2}},...,s_{v_{V}}\}$ as output. In other words, $\mathcal{S}=f(\mathbf{A})$, which enables us to rank nodes based on their scores and obtain any desired quantity of critical nodes without specifying the number in advance.

This node scoring function is obtained through our proposed evolutionary algorithm empowered by large model models.
Based on the given initial functions $\mathcal{F}_{0}=\{f_{0_{1}},f_{0_{2}},...,f_{0_{M}}\}$, our model generates some new functions during the training process through crossover and mutation.
To assess the fitness of these functions, we introduce an evaluation algorithm $\operatorname{E}$, which determines whether a function’s scores for nodes are reasonable, enabling us to update and eliminate functions accordingly.
Therefore, the evaluation algorithm $e$ explicitly defines the significance of "critical nodes" within the network.
In the end, many excellent node scoring functions $\mathcal{F}_{T}=\{f_{T_{1}},f_{T_{2}},...,f_{T_{N}}\}$ are retained within the population, and we select the one with the highest fitness as the model’s output.

## 3 Methodology

Figure: Figure 1: Illustration of our proposed model.
Refer to caption: x1.png

In order to discover a brand new excellent node scoring function, our model is based on evolutionary algorithms, combined with the powerful contextual understanding and programming capabilities of LLMs.
Through generation, evolution, evaluation, and iteration, we obtain a novel high-performance function.
It primarily consists of three components: Manual Initialization, LLMs-based Evolution, and Population Management.
Figure 1 and Algorithm 1 illustrate the framework of our model.

### 3.1 Manual Initialization

Evolutionary algorithms is a class of population-based stochastic search strategies.
The population initialization provides potential individuals for the entire search process.
These initial individuals continually iterate and improve during the training process, getting closer to the optimal solution.
A well-designed initialization can assist evolutionary algorithms in finding the optimal solution, particularly when dealing with large-scale optimization problems using finite-sized populations.
Therefore, we categorize the design approaches for node scoring functions into two classes as follows.

- •
Network Topology-based Function:
Network topology encompasses the connectivity relationships among nodes, and critical nodes often exhibit distinct connectivity patterns compared to other nodes.
In this section, we assign corresponding scores to nodes based on their centrality metrics, such as the number of N-hop neighbors of a node, the number of shortest paths in which a node lies, and the reciprocal of the sum of shortest paths from a node to all other nodes.
Because of the availability of comprehensive library functions, some centrality metrics can now be directly utilized.
To achieve a balance between the scalability and readability of the node scoring function, we choose not to rely solely on concise library functions for node scoring; instead, we have designed some functions that include detailed computation processes.
- •
Algorithmic Method-based Function:
Many classical algorithms analyze network characteristics through mathematical or statistical methods, and they identify critical nodes to dismantle the network based on the results of analysis.
These methods often incorporate greedy algorithms, the efficiency of which is closely related to the network size and the number of selected nodes.
In this work, we retain the core ideas of these algorithms and manually rewrite them into an efficient node scoring function as our initial approach.
It is worth noting that we did not consider learning-based methods because they typically require significant computational resources, which contradicts our goal of having a concise, clear, and fast node scoring function.

Based on the two approaches described above, we designed $M$ initial functions $\mathcal{F}_{0}=\{f_{0_{1}},f_{0_{2}},...,f_{0_{M}}\}$, each with a different emphasis in scoring nodes, all of which can serve as independent populations $\mathcal{P}=\{P_{1},P_{2},...,P_{M}\}$ to start evolution. The input and output of the node scoring function have been defined in Section 2 as $f(\mathbf{A})=\{s_{v_{1}},s_{v_{2}},...,s_{v_{V}}\}$.

### 3.2 Population Management

To maintain diversity within the function population, avoid falling into local optima, and simultaneously improve the performance of functions, we implement a sophisticated management strategy for the function population.

Figure: Algorithm 1 Algorithm of LLMs+EA

#### 3.2.1 Evaluation

Given a node scoring function $f\in\mathcal{F}$, our model first conducts a fitness assessment, which is closely related to our specific task — identifying critical nodes in the network through the learned function. Therefore, we define the node scoring function’s fitness evaluation as follows:

$$ $\operatorname{E}(f)=\sigma\left(\mathbf{A},\text{SORT}\left(f(\mathbf{A}) \right)[:L]\right)\text{,}$ (1) $$

where SORT represents a function that sorts nodes in descending order based on their scores, $[:L]$ indicates selecting the top L elements from the sorted list, and $\sigma$ stands for a function that evaluates the network state after removing nodes.
Through this evaluation function, each executable node scoring function obtains a suitable fitness score $c_{f}=\operatorname{E}(f)$, which assists us in better-performing selection and managing the functions population.

#### 3.2.2 Classification

While some functions have low fitness, they can introduce diverse potential evolutionary directions to the population.
Conversely, high-fitness functions already have numerous similar individuals, but their widespread presence often indicates a tendency to get trapped in local optima.
Considering the above situation, we further classify the node scoring functions $F$ based on their fitness scores.

Inspired by natural language processing tasks, we utilize pre-trained language model to process function $f\in\mathcal{F}$ into embeddings $\mathbf{z}_{f}$, which contain the syntax structure and semantic information of the code.
Subsequently, we calculate the cosine semantic similarity $\operatorname{S}(\mathbf{z}_{f},\mathbf{z}_{P_{i}})$ between the function and the existing population as follows:

$$ $\operatorname{S}(z_{f},z_{P_{i}})=\frac{\mathbf{z}_{f}\cdot\mathbf{z}_{P_{i}}} {\|\mathbf{z}_{f}\|\|\mathbf{z}_{P_{i}}\|}\text{,}$ (2) $$

$$ $\mathbf{z}_{P_{i}}=\frac{1}{|P_{i}|}\sum_{f\in P_{i}}\mathbf{z}_{f}\text{,}$ (3) $$

where $\mathbf{z}_{P_{i}}$ represents the average of function vectors within population $P_{i}$.
At the same time, we establish a similarity threshold $\tau$. Let

$$ $i^{*}=\arg\max_{i}\operatorname{S}(z_{f},z_{P_{i}})\text{,}$ (4) $$

if $\operatorname{S}(z_{f},z_{P_{i}})>\tau$, $P_{i^{*}}=P_{i^{*}}\cup\{f\}$;
otherwise, this distinctive function initiates a new population $P_{\text{new}}$. It is worth noting that each population has a limit on the number of individuals. Once a population reaches its maximum capacity, any newly added function must have a higher fitness score to replace the existing lowest-scoring function, thereby maintaining the population’s high performance.

#### 3.2.3 Selection

We implemented two designs for selection of parent functions within the population, namely, intra-population selection and inter-population selection.

- •
Intra-population selection:
Considering the diversity of functions, our model selects one individual from each population to serve as intra-population parent functions $\mathcal{F}_{\text{intra}}$ in each selection. At the same time, to maintain elite individuals, the highest-fitness function is also added to $\mathcal{F}_{\text{intra}}$.
- •
Inter-population Selection:
Taking into account the fitness of functions, two functions are chosen from the same population to serve as inter-population parent functions $\mathcal{F}_{\text{inter}}$ in each selection, allowing subsequent crossover operations to discover differences between functions of the same population but with different fitness scores.

In both selection methods, the fitness scores of each function serve as selection weights, encouraging the selection of more excellent individuals. For convenience, we use $\mathcal{F}_{\text{parent}}$ to represent $\mathcal{F}_{\text{intra}}\cup\mathcal{F}_{\text{inter}}$.

Figure: Figure 2: Prompts used in the crossover and mutation.
Refer to caption: x2.png

### 3.3 LLMs-based Evolution

Given the parent functions, our model begins the evolution process to generate new functions.
The traditional crossover and mutation operators used in programming struggles to make high-quality modifications to functions like human programmers do.
In contrast, LLMs trained on extensive data including code, documentation, tutorials, and more, can comprehend complex programming tasks and perform high-quality code modifications and generation.
Therefore, we use LLMs as the operators to cross and mutate the given functions to generate offspring codes.

#### 3.3.1 Crossover

The inputs for crossover consist of a set of selected parent functions $\mathcal{F}_{\text{parent}}$, and the outputs are a set of offspring functions $\mathcal{F}_{\text{off}}$.
The prompts provided for LLMs include the functions and their scores, as well as a text-formed description of crossover requirement and additional format-related constraints. We aim for the LLMs to focus on analyzing the distinctions and relationships among functions. Therefore, we have not provided any descriptions related to the network or the task of identifying critical nodes, to avoid causing any interference. The formula for the crossover is shown below:

$$ $\mathcal{F}_{\text{off}}=\operatorname{LLM}(\mathcal{F}_{\text{parent}},C_{ \text{parent}},prompt_{\text{cross}}){,}$ (5) $$

where $C_{\text{parent}}=\{c_{f},\forall f\in\mathcal{F}_{\text{parent}}\}$ represent the set of fitness scores of all parent functions.

#### 3.3.2 Mutation

For the diversity of the population, each offspring function $f\in\mathcal{F}_{\text{off}}$ has a certain probability $\theta$ of undergoing mutation. The prompts provided as inputs for LLMs include the offspring function and a text-formed description of mutation guiding and format requirements, and the output are a set of mutant functions $\mathcal{F}_{\text{mutate}}$. Similarly, to keep LLMs focused on the code, our prompts do not contain any descriptions related to the task background. The mutation formula is as follows:

$$ $\mathcal{F}_{\text{mutate}}=\operatorname{LLM}(\mathcal{F}_{\text{off}},prompt _{\text{mutate}}){.}$ (6) $$

Figure 2 illustrates the detailed prompts used in the crossover and mutation. The generated functions $\mathcal{F}_{\text{off}}$ and $\mathcal{F}_{\text{mutate}}$, after undergoing executable checks, are systematically added to the population following the evaluation and classification described in Section 3.2. This process repeats iteratively, with the entire function population gradually growing until ideal function emerges.

## 4 Experiments and Results

In this section, we aim to comprehensively evaluate the proposed model by providing detailed responses to the following research questions (RQs):

- •
RQ1: Can our proposed method outperform existing baselines in terms of performance?
- •
RQ2: Which functions does our model discover, and are they identical?
- •
RQ3: Through what processes does our model derive these functions?
- •
RQ4: How effective is each component within our proposed model?

### 4.1 Experimental Settings

#### 4.1.1 Experimental environment

We compared the performance of our best algorithm obtained from LLMs+EA with numerous traditional methods on both real-world and synthetic networks, including both machine learning-based methods and algorithmic approaches. We contrasted the disruptive impact on the networks during the removal of 20% of nodes under the ANC metric. The entire model is implemented in Python and runs on Intel Xeon Platinum 8358. We use the hyperparameters in Table 1 for LLMs+EA runs, and each dataset requires approximately two dollars with gpt-3.5-turbo for three hours.

**Table 1: Hyperparameters of LLMs+EA**
| Hyperparameter | Value |
| --- | --- |
| LLM (crossover and mutation) | gpt-3.5-turbo-0613 |
| LLM temperature (crossover and mutation) | 1/1.5 |
| Number of initial populations | 10 |
| Maximum population size | 10 |
| Maximum number of epoch | 100 |
| Mutation rate | 0.3 |
| Code2Vec model | bert-base-uncased |
| Similarity threshold | 0.93 |

#### 4.1.2 Metrics

Given a network $\mathcal{G=(V,E)}$, with its node set as $\mathcal{V}$ and edge set as $\mathcal{E}$, and a connectivity measure as $\mathcal{\sigma}$, the accumulated normalized connectivity (ANC) is defined as follows:

$$ $R(v_{1},v_{2},\cdots,v_{N})=\frac{1}{N}\sum_{k=1}^{N}\frac{\sigma(\mathcal{G} \backslash\{v_{1},v_{2},\cdots,v_{k}\})}{\sigma(\mathcal{G})}\text{,}$ (7) $$

where $N$ is the total number of the nodes,and $\sigma$ is the widely used pairwise connectivity.The $\sigma:\{\mathcal{G}\}\to\{R^{+}\}$ is defined as:

$$ $\sigma(G)=\sum_{C_{i}\in G}\frac{|C_{i}|(|C_{i}|-1)}{2}\text{,}$ (8) $$

where $C_{i}$ is the $i$th connected component in network G,and $|C_{i}|$ means the number of nodes in the subgraph $C_{i}$. Our goal is to find a removal list that can minimize the ANC of a given network after removing selected nodes.

#### 4.1.3 Baselines

We compare our proposed method with the following competitive baselines:

- •
DC (Degree Centrality): A heuristic method that iteratively removes nodes with the highest degrees.
- •
GNDR : Employs a spectral approach to iteratively partition the network into two components.
- •
MinSum : Initially creates an acyclic network by removing nodes that form loops, then employs greedy tree-breaking algorithms to decompose the resultant forest into smaller, disconnected components.
- •
CoreHD : Utilizes a k-core decomposition strategy, where the k-core of a network denotes the maximal subgraph in which every node has a degree of at least k. CoreHD progressively removes nodes with the highest degrees within its k-core to select key nodes.
- •
WN (Weak Neighbors) : This algorithm improves upon CoreHD by selecting, for deletion, the neighbor node with the minimum degree when multiple nodes have the maximum degree in a k-core. Conversely, CoreHD randomly selects one of the nodes with the maximum degree within a k-core for deletion.
- •
VE : Incorporating concepts from quantum mechanics, VE utilizes an entanglement-based metric to quantify the perturbations that individual vertices induce in spectral entropy, and it identifies key nodes based on these measurements.
- •
GDM : This machine learning-based approach uses graph convolutional networks to understand the topological structure of networks and to evaluate the likelihood of node attacks. It is trained on small-scale virtual networks, showing favorable transferability to large-scale and real-world networks.
- •
NIRM : This machine learning-based method conducts a comprehensive assessment of both global and local node features in the network, effectively identifying critical nodes.

**Table 2: Statistics of networks**
| Network | Jazz | Twitter | Network Science | Synthetic Network |
| --- | --- | --- | --- | --- |
| $|V|$ | $198$ | $475$ | $1,565$ | $1,000$ |
| $|E|$ | $2,742$ | $13,289$ | $13,532$ | $2,991$ |

#### 4.1.4 Datasets

We selected the following datasets to evaluate our method and baselines, the statistics of which are detailed in Table 2.

- •
Jazz : Represents a collaboration network among Jazz musicians, where each node corresponds to a musician, and an edge signifies that two musicians have collaborated in a band.
- •
Twitter : This dataset quantifies the pairwise probability of influence within a Congressional Twitter network.
- •
Network-Science : Constitutes a co-authorship network within the field of network science.
- •
Synthetic Network: A Barabási-Albert $(m=3)$ network, randomly generated with 1000 nodes.

### 4.2 Overall Performance Comparison (RQ1)

**Table 3: Overall performance of our method. The ANC presented here represents ANC score of networks post the removal of 20% of nodes selected by each method and a lower ANC indicates greater efficacy.**
| Methods<br>Datasets | Jazz | Network Science | Twitter | Synthetic Network | Average Rank |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| ANC | rank | ANC | rank | ANC | rank | ANC | rank |  |  |
| LLMs+EA | 0.65454 | 1 | 0.05326 | 2 | 0.80762 | 2 | 0.65495 | 2 | 1.75 |
| DC | 0.79066 | 8 | 0.11842 | 9 | 0.81125 | 4 | 0.67685 | 5 | 6.5 |
| GNDR | 0.69697 | 2 | 0.05330 | 3 | 0.80799 | 3 | 0.70592 | 7 | 3.75 |
| MinSum | 0.79414 | 9 | 0.05291 | 1 | 0.80535 | 1 | 0.65613 | 3 | 3.5 |
| CoreHD | 0.78833 | 5 | 0.09932 | 7 | 0.81125 | 4 | 0.73633 | 8 | 6 |
| WN | 0.78833 | 5 | 0.10325 | 8 | 0.81125 | 4 | 0.73795 | 9 | 6.5 |
| VE | 0.74837 | 3 | 0.08583 | 6 | 0.81125 | 4 | 0.68259 | 6 | 4.75 |
| GDM | 0.78417 | 4 | 0.05908 | 4 | 0.81125 | 4 | 0.65384 | 1 | 3.25 |
| NIRM | 0.78855 | 7 | 0.06781 | 5 | 0.81125 | 4 | 0.67446 | 4 | 5 |
| Data highlighted with yellow means its method performs the best on the network, while the bolded data’s method is the second best. |  |  |  |  |  |  |  |  |  |

First, we implement our proposed model and baseline methods on each network dataset, subsequently selecting 20% of the total nodes from each network. Following this, we exclude these nodes from the network and compute the ANC for each case. Table 3 presents a comparison of the overall performance. Based on these results, we make the following observations:

- •
The performance of baselines varies across networks.
The effectiveness of baseline methods differs significantly among networks, where a lower ANC value reflects a more substantial impact on network connectivity. Specifically, GNDR outperforms others in the Jazz network, followed by the learning-based method VE, with the remaining approaches closely trailing. Notably, MinSum shows the least effectiveness here. Conversely, in the Network Science dataset, the generally low ANC values suggest a pronounced effect on network connectivity by all baseline methods, with MinSum leading in performance and the heuristic DC lagging behind. In the Twitter network, MinSum continues to excel, although the ANC values for all methods are tightly grouped, indicating less differentiation in the identification of critical nodes. Remarkably, six baselines yield identical ANC values in this context, underscoring the distinct nature of critical nodes within the Twitter network. For the synthetic network, GDM emerges as the most effective, whereas Weak-Neighbors falls short.
- •
Superior Overall Performance of Our Model.
Our method distinguishes itself by surpassing all competitors in the Jazz dataset by a notable margin and maintaining robust performance in the Network Science, Twitter, and synthetic networks, consistently ranking as a close second to the best-performing methods. Interestingly, MinSum, despite its top-tier results in the Network Science and Twitter datasets, ranks at the bottom in the Jazz dataset, highlighting its inconsistent efficacy across different networks. The uniform excellence of our model across diverse networks suggests its capability to more accurately score nodes, thereby more effectively identifying critical nodes within any given network.

### 4.3 Function Analysis (RQ2)

We present the optimal node scoring functions derived from the Jazz and Network-Science datasets in Figure 3. For Jazz, the premier scoring function assesses nodes by integrating local features with centrality measures. It begins by computing the network’s largest connected component to derive a Laplacian matrix (lines 4, 9–10). Utilizing this matrix, the function proceeds to compute the Fiedler vector, employing it to establish a new graph (lines 11–13). This new graph identifies a minimum weighted cover to assign scores to its nodes (lines 13–22). Nodes not included in this new graph receive scores based on normalized eigenvector centrality (lines 5–8, 24).

Figure: Figure 3: The best functions found on Jazz and Network-Science.
Refer to caption: x3.png

Conversely, the superior node scoring function from the Network-Science dataset determines node scores by calculating degree-related metrics (lines 4–8), betweenness centrality (line 9), and PageRank values (line 10) independently. These metrics are then aggregated using weighted averages to calculate a comprehensive node score (lines 11–19), effectively merging various centrality measures for node evaluation.

This analysis reveals that the scoring functions our method uncovers differ across networks, all originating from manually designed initial functions and undergoing diverse modifications to logically score nodes. Additional discovered functions are accessible here: [https://anonymous.4open.science/r/LLM4CN-6520](https://anonymous.4open.science/r/LLM4CN-6520).

Figure: (a) Population Size Heatmap
Refer to caption: x4.png

### 4.4 Case Study (RQ3)

Figure 4 illustrates the statistics of function populations during the training process on the synthetic network, aiding us in understanding the evolutionary process of the function populations. Figure (a), (b) and (c) respectively represent the evolution of the population size, the average fitness score, and the highest fitness score of each function.

First, in terms of population size, as evolution progresses, the majority of populations incrementally increase, reaching their respective capacities and initiating updates via elimination. However, for Population 2, the function count consistently remains at one, indicating the absence of similar offspring function generation. Given that Population 2’s score is the lowest among all initial functions, it logically follows that its inferior genes are not selected. Furthermore, two new populations emerged during evolution, illustrating our population management design’s capability to preserve the diversity of function populations.

Moreover, the analysis of change curves for average and highest fitness scores across populations reveals continuous enhancement in the overall function quality.
Simultaneously, no instances of multiple populations maintaining the same average fitness throughout evolution were observed, indicating our design’s effectiveness in circumventing the pitfall of convergent evolution. Around the 20th and 100th epochs, there are noticeable increases in the fitness scores of the function populations, representing the circulation of superior genes within the populations and enhancing overall performance.

In conclusion, our proposed model ensures that the function populations can evolve continuously while preserving diversity, thereby facilitating the generation of superior new functions.

### 4.5 Ablation Study (RQ4)

We conduct ablation studies to evaluate the effectiveness of a node scoring function in identifying critical nodes within a network. Our model is built upon three key components, and through ablation, we aim to assess the impact of each component as described below.

Figure: Figure 5: Comparison of ablation study.
Refer to caption: x7.png

- •
W/O Manual Initialization: To gauge the significance of Manual Initialization, we adopt an alternate strategy. Here, we define the task of identifying critical nodes to the LLM and instruct it to generate an equivalent number of node scoring functions in a predetermined format, thereby bypassing manual initialization.
- •
W/O Population Management: To explore the necessity of Population Management, we implement an alternative scheme where all functions are collected without any categorization. During the selection phase, parent functions are randomly selected from the entire pool of individuals, eliminating structured population management.
- •
W/O LLMs-based Evolution: Assessing the indispensability of LLMs-based Evolution, we introduce an alternative method. Initially, all functions are treated as parent functions. This is followed by a single epoch of crossover and mutation to produce a multitude of offspring functions, from which the most suitable are chosen, simulating a condensed version of the evolutionary process.

The efficacy of the node scoring functions discovered via each ablation strategy versus the comprehensive method was analyzed. Findings, depicted in Figure 5, affirm that every component of our proposed model significantly enhances its overall performance.

## 5 Related Work

### 5.1 Synergy between LLMs and EAs

Recent research underscores the effectiveness of leveraging Large Language Models (LLMs) for optimization tasks via prompt engineering ; . This method proves particularly advantageous for Evolutionary Algorithms (EAs), attributed to the advanced text comprehension and generation capabilities of LLMs ; . For example, recent investigations into discrete prompt optimization have shown how LLMs can mimic evolutionary operators, generating innovative candidate prompts through crossover and mutation based on fixed prompts ; . Furthermore, studies have explored the use of LLMs in tackling combinatorial optimization problems (COPs) by developing evolved heuristic solutions ; . EvoPrompting utilizes LLMs for Neural Architecture Search (NAS), performing crossover and mutation at the code level to discover new architectures. Likewise, FunSearch implements an LLM-powered evolutionary method to determine solution functions for mathematical challenges. In addition, Eureka focuses on the design of reinforcement learning reward functions using LLM-based evolutionary algorithms, while Fuzz4All applies LLMs in fuzz testing to generate and mutate inputs.

Distinct from previous studies, our research emphasizes the use of LLMs that perform mutation and crossover processes on node scoring functions, aiming to evolutionarily determine the most effective scoring functions.

### 5.2 Critical Nodes Detection

Identifying critical nodes is of significant importance across various practical domains. Numerous approaches have been proposed to tackle this issue.
Basic methods such as Degree Centrality, entail removing nodes with the highest degrees.
Algorithms like CoreHD and WeakNeighbors utilize k-core decomposition, in which the k-core of a network is defined as the maximal subgraph with every node having a degree of at least k. These methods progressively eliminate nodes with the highest degrees within their respective k-cores to identify key nodes. On the other hand, Min-Sum focuses on creating an acyclic network by removing nodes that form loops, followed by utilizing greedy tree-breaking algorithms to decompose the remaining forest into smaller disconnected components. Additionally, GND adopts a spectral approach to iteratively partition the network into two components. Learning-based methods like NIRM and GDM utilize neural networks to assign scores to network nodes, determining their importance based on these scores.

Unlike previous studies, our research is not limited to identifying specific algorithms. Rather, it leverages LLM-empowered Evolutionary Algorithms (EAs) to investigate a broad spectrum of potential algorithms, yielding favorable outcomes across diverse networks.

### 5.3 LLMs for Code Generation

Large Language Models (LLMs) exhibit considerable promise in automating code generation, capitalizing on their capacity for training on vast repositories of publicly available source code. This training enables them to acquire a comprehensive understanding of programming concepts and patterns, which in turn significantly enhances their capabilities in code generation ; . These capabilities are progressively applied to tackle a multitude of code-related challenges. Notably, LLMs are employed in tasks such as code debugging ; , enhancing code performance , resolving algorithmic competition problems ; , and conducting code deobfuscation ; and translation ; . Additionally, the capacity to produce task-specific code highlights the versatility of LLMs; for instance, their deployment in robotics control ; , domain-specific data curation , and solving general tasks ; , illustrates their extensive utility across specialized and general domains.

In this paper, we explore in depth the potential of code generation in efficiently identifying optimal scoring functions through the use of LLM-based evolutionary algorithms (EAs).

## 6 Conclusion and Future Work

In this study, we employ an evolutionary algorithm enhanced by large language models for generating node scoring functions, to identify critical nodes within networks. Initially, the evolution begins with a set of functions crafted based on network topology and existing algorithmic approaches. Subsequently, the model assesses the fitness scores of the given functions within the network and categorizes populations according to the embedding representations of these functions. Following this, selections both between and within populations are performed to select parent algorithms for further evolution. Finally, the LLMs are utilized to execute crossover and mutation operations, producing offspring individuals. Following executable checks, newly generated functions are incorporated into the population, and this iterative process persists until the evolution terminates.

Experimental results across various network datasets reveal that our method effectively balances adaptability and utility in comparison to other state-of-the-art algorithms. It is capable of generating a variety of both reasonable and efficient node scoring functions.

In future work, we aim to delve deeper into distributed designs for the evaluation, management, and evolution processes, enabling parallel execution to improve the model’s evolutionary speed and performance. Furthermore, we plan to diversify the types of initial algorithms and prompts, aiming to create more compelling, high-performance node scoring functions through large language models, focusing on the identification of critical nodes within networks.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. How are the prompts developed? How does it impact the generated functions?
2. Are there specific network properties where this approach underperforms compared to baselines, and how could these be addressed? 
3. Can this approach be optimized for efficiency so that could make the approach more practical for large-scale applications?
soundness: 3
strengths: 1. The paper presents a novel approach to identifying critical nodes in a network using LLMs for code generation. 
2. The authors cast the critical node generation problem as a code generation problem where LLMs can generate node scoring functions that can potentially adapt to different network structures. 
3. The authors introduce a population management approach that uses semantic analysis and metrics on function embeddings to maintain diversity in the function population. 
4. The proposed approach performs well in the experiments
summary: This paper presents a framework combining Evolutionary Algorithms (EAs) and Large Language Models (LLMs) to identify critical nodes in complex networks. The EA’s search space consists of functions that score nodes based on information from the network's adjacency matrix. The framework includes three modules: Manual Initialization, Population Management, and LLM-based Evolution. In the first module, initial scoring functions are generated using network topology or mathematical methods to target nodes whose removal would dismantle the network. The second module assesses functions based on fitness and semantic analysis to select parent functions for the next generation. Finally, the third module uses LLMs for evolution, applying crossover and mutation to generate new functions from the parent functions. Experimental results on real-world and synthetic networks suggest this approach outperforms other baseline methods, producing diverse and effective node-scoring functions.
weaknesses: 1. The authors may consider testing LLM’s robustness for varying network structures and properties and share the insights and the limitations. 
2. The authors may consider implementing an interpretability mechanism, such as feature importance analysis, to understand which generated functions are more effective on which network structures.  
3. The authors are encouraged to provide a more comprehensive discussion of the limitations of this approach.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: I would like to know what the initialization functions include, whether they include a baseline, and if there are initialization functions that exceed baseline performance. I hope to see experimental results that illustrate the ANC_gcc performance of these initialization functions before any iterations. 

I would like the author to conduct an ablation study on the best function to analyze which computational process contributes to the significant performance improvement and which initialization function this process is derived from.
soundness: 3
strengths: 1. Introduces a new perspective by integrating LLMs with EAs to transform the critical node detection problem into a code-generation task.
2. Proposes a general framework that combines LLMs and evolutionary learning, along with a generation-update mechanism for LLMs and crossover-mutation methods for evolutionary learning.
summary: This paper proposes a method that combines large language models with evolutionary algorithm concepts to generate a "score_nodes" function. This function can provide evaluation scores for each node and is used to identify critical nodes in complex networks. The method comprises three parts: Manual Initialization, Population Management, and LLMs-based Evolution. Manual Initialization initializes various existing functions. Population Management involves dividing the population based on similarity and evaluating the functions' fitness. Based on the population and fitness, it generates intra-population selection and inter-population selection for each iteration. Large language models are used to analyze similarities and differences within and between groups to generate a new generation of functions.
weaknesses: 1. The experimental results show that the author's method significantly outperforms other baselines, while the performance of all other baselines is similar. This raises concerns about the experimental results, as the author does not provide a detailed analysis or explanation of the source of such a significant improvement (i.e., which computational processes contribute to it). 

2. Ablation studies indicate that manual initialization has a substantial impact on the method's effectiveness. This raises the question of whether the entire generation process relies on very strong prior knowledge, possibly even containing initialization functions that surpass all baseline methods.

3. The manual initialization process might require significant expertise and could be a bottleneck in applying the model to different networks without prior knowledge.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: - What does 3.2.2 have to do with "classification”? Isn’t it just a diversity focused fitness augmentation? I would appreciate this being explained in a bit more depth. 
- How general can you expect this method to perform? It seems as though you are catering a specific function for each dataset, which strikes me as somewhat brittle. Do you expect that functions found for one task can generalize to others? If so, I would like to see that as an additional result. If not, I would like that to be made more clear.
- Is there any chance that the solutions for the datasets used exist in the LLM training data?
soundness: 3
strengths: - The paper is relatively easy to follow.
- Comparisons are made to a large number of baselines, proving experimental rigor.
- The results are consistent, and prove the key conclusions of the paper well. 
- I appreciate the function analysis and case study, showing that techniques based on code generation can improve on the interpretability of our machine learning methods.
summary: This paper focuses on using Large Language Models in an Evolutionary Algorithm to write code that can identify critical nodes in complex networks. This paper presents an algorithm that uses LLMs as the mutation and reproduction operators for code in an evolutionary framework. To do this, the authors prompt a language model to combine or mutate given models for use in an evolutionary algorithm. The authors compare the proposed approach to a variety of baselines, and use six different datasets to evaluate the method. The results show relatively consistent improvements for using the proposed approach over prior work.
weaknesses: - While the use-case is novel to my knowledge, the use of an LLM as the mutation operator for an evolutionary algorithm framework is not novel, and has not been adequately framed in relation to prior work (ELM, etc). [1]
- This work seems like a very narrow use case. I would have liked to see whether this method can adapt to other network based domains.  
- Although there is an ablation study, I don’t find it convincing as evidence for the use of such as sophisticated population management framework. The authors did not well advocate for their choices in the use of initialization and population management. From the appendix, it appears that the ablation for population management simply removes any selection pressure through the use of random selection. I suggest modifying this ablation to simply use a normal evolutionary algorithm with a population of candidates that is selected from and mutated/reproduced over time.

[1] Lehman, J., Gordon, J., Jain, S., Ndousse, K., Yeh, C. and Stanley, K.O., 2023. Evolution through large models. In Handbook of Evolutionary Machine Learning (pp. 331-366). Singapore: Springer Nature Singapore


Small notes:

- Citations are incorrectly formatted throughout. (citep instead of cite)
    
- Many small grammatical errors and awkward phrasings
    - e.g “The first kind of work is the basic methods based on heuristics”
    - e.g. “LLMs-based” should be “LLM-based”
        
- There is a lack of relation to prior work on using evolutionary algorithms for code generation. It would have been nice to comment on the differences between this approach and previous techniques such as Genetic Programming.
- Section 3.2 is difficult to follow.
- The intermixing of singular and plural for population is confusing. For example, in section 3.2 -- is there one population or many throughout evolution? I would recommend changing the name of population (meaning the inner population) to something more fitting like “species”, for example.
- I assume from the phrase “the fitness scores of each function serve as selection weights,” that the authors are using fitness proportionate selection. I would have liked this to be more clear.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 1
questions: 1. Could you provide a runtime analysis comparing your method against baseline approaches, particularly GNDR? Given the additional complexity from LLM operations, evolutionary epochs, and population management, understanding the computational tradeoffs relative to a simpler spectral method seems crucial for evaluating practical utility.
2. Could you justify comparing against only a single epoch of traditional evolution in the ablation study? A more thorough comparison showing how LLM-based operations differ qualitatively from traditional genetic operators over multiple epochs seems necessary to demonstrate the value of LLMs in this context.
3. Could you provide the missing implementation details for the (a) criteria for splitting initial functions between topology-based and algorithm-based approaches, (b) clarification regarding how your crossover+mutation population management strategy differs from those outlined in your related work section, and (c) exact prompting strategy and constraints used for LLM-based evolution, for example whether the resulting LLM output was always a valid function, and what you did in that case?
4. More generally, given the related work you discuss on LLM-guided evolution and optimization (e.g., Guo et al., Li and Wu), how does the EA part of your approach compare to or build upon these methods?
soundness: 2
strengths: 1. The paper presents an innovative reformulation of critical node identification as a code generation task guided by LLMs and evolutionary algorithms, demonstrating a novel approach to this NP-hard problem
2. The empirical results across diverse network types (from social networks to power grids) suggest this paradigm of using LLMs to generate and evolve scoring functions could be valuable for similar combinatorial optimization problems
3. By combining LLMs with evolutionary search, the paper introduces an interesting framework for exploring the space of possible node scoring functions
summary: This paper presents an approach combining Large Language Models (LLMs) with evolutionary algorithms to generate scoring functions for identifying critical nodes in networks. The paper proposes:

- A framework that uses LLMs to generate and evolve functions that assign importance scores to network nodes
- A population management system that classifies functions using semantic similarity and implements both intra- and inter-population selection
- An evolution mechanism where LLMs perform crossover and mutation operations on the scoring functions
- Empirical results comparing the method against 9 baseline approaches across 6 networks using two metrics (ANCgcc and ANCpc)
- Ablation experiments examining the effects of removing each component (manual initialization, population management, LLM-based evolution)

The work includes performance benchmarks on several network datasets (Jazz, Twitter, Network Science, Synthetic Network, Power Grid, LastFM), analysis of the generated scoring functions, and documentation of the implementation including hyperparameters and experimental configuration. The authors aim to address what they term the "adaptability-utility dilemma" in critical node identification, where methods typically trade off between adaptability to different network types and computational efficiency.
weaknesses: 1. The method's practical value is undermined by inadequate runtime analysis. While the approach achieves good accuracy metrics, GNDR achieves strong performance (average rank 3.0) across datasets with much lower computational requirements. Without any analysis of end-to-end runtime comparisons, it's difficult to evaluate whether the additional complexity is warranted.

2. The ablation study comparing against a single epoch of traditional evolutionary operators provides insufficient evidence for the value of LLMs in this context. While the constraints of traditional evolutionary operators may differ from LLM-based ones, a more thorough comparison should include multiple epochs of traditional evolution (if computationally feasible) and analysis of how LLM-based operations differ qualitatively from traditional genetic operators.

3. Several key methodological components are inadequately described. The criteria for splitting initial functions between topology-based and algorithm-based approaches is unspecified, the population management mechanism's specific implementation is omitted beyond high-level descriptions, and the exact prompting strategy and constraints for LLM-based evolution are not detailed. Perhaps all the necessary details are included, but a full algorithm for the entire procedure is not present anywhere I could see.

4. Despite presenting a related work section on LLM-guided evolution and optimization (e.g., Guo et al., Li and Wu), the authors don't compare against or build upon these approaches. The paper discusses numerous relevant techniques for LLM-based evolutionary operators and combinatorial optimization but doesn't justify why their specific approach is preferable to or different from these established methods. This makes it difficult to assess the true contribution beyond applying existing techniques to a new domain.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. The writing could be refined with more precise and widely accepted terms from the literature.
2. In line 106 of page 2, the authors state that a well-designed population initialization strategy can help identify optimal solutions, particularly for large-scale tasks with a limited population size. However, it is important to note that in many cases, initialization strategies primarily enhance convergence speed rather than directly improving solution quality. It would be beneficial for the authors to provide citations supporting this claim. Additionally, it is unclear whether the proposed problem is indeed large-scale.
3. Several technical aspects require further clarification, including the motivation for using multiple populations and the challenges associated with applying existing EAs to the proposed problem. Additionally, the LLMs may generate inappropriate or even erroneous prompts for crossover and mutation operations. It is unclear how the authors address these potential issues in their approach. 
4. Including a workflow diagram/pseudocode.
soundness: 2
strengths: 1. The authors utilize Evolutionary Algorithms (EA), a gradient-free optimization method, for this domain-specific application.
2. The authors introduce a novel approach to the variation step in Evolutionary Algorithms (EA) by leveraging Large Language Models (LLMs), extending their use beyond traditional question-answering applications.
3. Figures 1 and 2 are well designed to help readers understand the workflow of the proposed method.
4. Research Questions 1–4, outlined in Section 4, clearly show readers the structure of the subsequent content.
summary: This paper introduces a new mechanism for generating scoring functions to identify critical nodes in networks. Specifically, the authors employ EA and LLM to produce node scoring functions in an optimization manner. The approach begins with an enhanced population initialization strategy. Following this, an LLM-based variation mechanism is implemented to evolve scoring functions. Finally, an inter- and intra-population selection strategy is applied to select the most promising functions for the next iteration. Experimental results demonstrate the superior performance of the proposed method.
weaknesses: 1. This paper integrates several existing methods, including LLMs and EAs. While the authors adapt EAs specifically for their critical node detection problem, the challenges and difficulty of this customization are not thoroughly demonstrated. 
2. The expressions in the paper could benefit from more precise, domain-specific terminology. 
For example, to the best of my knowledge, ‘combinatorial optimization’ and ‘evolutionary learning’ are more commonly accepted terms than ‘combinational optimization’ and ‘evolutional learning’. Phrases like ‘optimal search task’ are somewhat unclear. Using well-established terms from optimization theory or operations research would make the text more readable and aligned with standard terminology in the field. 
3. Several established methods from the current field of Evolutionary Algorithms (EA) could be leveraged in this paper. For instance, the subset selection problem is a well-known combinatorial optimization task, and related optimization algorithms might be applicable to this paper’s objectives. However, the discussion of existing EA research relevant to this optimization task is missing in the current paper.
4. The authors employ a multi-population strategy during optimization, which is uncommon in Evolutionary Algorithms (EA). Providing a discussion on the motivation behind this choice, along with evidence of its benefits, would strengthen the paper and enhance the reader's understanding.
5. Pseudocode or a diagram regarding the overall workflow of this work's method is not provided.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 3
questions: As both LLMs and evolutionary algorithms are with randomness, I am quite curious about the stability of the searched algorithm. Is it always able to find the algorithm achieving the same result as reported? Is there any statistic analysis?
soundness: 2
strengths: 1. This work leverages the NLP techniques to facilitate the LLMs-based algorithm generation, which may provide some insights to the related community.

2. The algorithm found by this work may provide some insights when designing efficient heuristic in solving network science tasks.
summary: This work use LLMs and genetic algorithm to generate the algorithms for the identification influential nodes in complex networks and the results shows the LLMs-generated algorithm is better than some of existing approaches across different datasets.
weaknesses: 1. The primary concern is the generalizability of this approach. While pioneering studies like [1,2] have demonstrated effectiveness across various combinatorial problems, this work is limited to a single-task focus. With this in mind, I suggest expanding the evaluation to include additional tasks, particularly in the area of complex networks, such as influence maximization and immunization.

2. The contribution is limited as there are already several works of LLMs-based algorithm generation and it would be good to see if there are more contributions in terms of structural design instead of just an application on a different task. 3.2.1 is a normal metric in network science area and 3.2.3 is very similar to [2].

3. The tested problem is also known as graph dismantling where the curve of the largest connected component should be plotted as the part of experiment.

4. Some key experimental setting is missing, such as crossover rate.

5. The citation format should be improved.

[1] Liu, Fei, et al. "Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model." Forty-first International Conference on Machine Learning. 2024.

[2] Romera-Paredes, Bernardino, et al. "Mathematical discoveries from program search with large language models." Nature 625.7995 (2024): 468-475.

Meta-review: This paper proposed a framework combining LLMs with Evolutionary Algorithms (EA) to generate  "score_nodes" function to identify the critical nodes in complex networks. 

Strengths:
1.  The idea of Integrating LLMs and EAs to address the critical node identification is interesting. 

2.  The authors provided results on different network types and metrics, and it shows some potential of the proposed method.

Weaknesses:

1. There is some overlaps with prior LLM-based combinatorial optimization methods.  

2. There is a lack of computational complexity analysis. 

3. Some concerns were raised on generalization and robustness of the method since current performance improvements seems to rely heavily on manual initialization. Additionally, the ablation studies are insufficient to validate the claimed contributions.

4. The paper is not well-written and some parts are unclear. For example, the population management and prompting strategies are not well explained.

While the idea is interesting, I have to recommend rejection in its current form but I sincerely encourage the authors to revise it before future submission.

Decision: Reject