Target Controllability Eval

target-controllability-eval

Identifying efficient controls of complex interaction networks using genetic algorithms — Popescu et al. (2020) (arXiv:2007.04853, 2020)

What this evaluates

Evaluates an algorithm's ability to identify minimal control input sets for steering complex networks to target states. It probes scalability, solution optimality, and the capacity to prioritize biologically relevant nodes (e.g., drug targets) across synthetic and biological interaction networks.

Datasets

• Breast DEF — total 1415; splits: test (1415); repo https://github.com/vicbgdn/GeneticAlgNetControl
• Breast HCC1428 — total 1495; splits: test (1495); repo https://github.com/vicbgdn/GeneticAlgNetControl
• Ovarian DEF — total 1047; splits: test (1047); repo https://github.com/vicbgdn/GeneticAlgNetControl
• Pancreatic AsPC-1 — total 1022; splits: test (1022); repo https://github.com/vicbgdn/GeneticAlgNetControl
• Social Interaction 1 — total 67; splits: test (67); repo https://github.com/vicbgdn/GeneticAlgNetControl
• Erdos-Renyi 1000 — total 1000; splits: test (1000); repo https://github.com/vicbgdn/GeneticAlgNetControl
• Scale Free 1000 — total 1000; splits: test (1000); repo https://github.com/vicbgdn/GeneticAlgNetControl
• Small World 1000 — total 1000; splits: test (1000); repo https://github.com/vicbgdn/GeneticAlgNetControl

Metrics

• solution_size (I) (primary) — range: integer
  • The cardinality of the minimum control input set found by the algorithm to steer the network to the target node set. Lower values indicate better optimality.
• preferred_node_count (IP) — range: integer
  • The number of nodes in the control set that belong to a predefined preferred set (e.g., FDA-approved drug targets). Higher values indicate better biological relevance.
• running_time_per_solution — range: seconds
  • Wall-clock time required for the algorithm to produce a valid control set on a given network.

Input / output format

Input: Directed graph represented as adjacency list/matrix, target node indices, and optionally a preferred node set (e.g., drug targets).

Output: Set of input node indices forming the control set.

Scoring recipe

def evaluate(control_set, target_set, preferred_set=None):
    is_valid = check_controllability(control_set, target_set)
    if not is_valid:
        return {'valid': False, 'solution_size': len(control_set)}
    solution_size = len(control_set)
    preferred_count = len(control_set & preferred_set) if preferred_set else 0
    return {'solution_size': solution_size, 'preferred_count': preferred_count}

Common pitfalls

• Comparing unconstrained vs constrained greedy baselines without matching path-length bounds leads to unfair advantage/disadvantage.
• Stopping criteria differ between algorithms (generations for GA vs iterations for greedy), making direct runtime comparisons sensitive to implementation details.
• Random graphs were generated with fixed parameters (e.g., p=0.005) that may not reflect real-world network distributions, limiting generalizability.

Evidence (verbatim from paper)

The first benchmark objective we compared against was the size of the smallest set of input nodes found by each of the three algorithms, with the smallest being the best. The results are presented in Table 3. We also compared the running time required by the algorithms to complete on each of the benchmark networks and the speed of convergence towards a good solution.

Citation

@misc{popescu2020geneticalgnetcontrol,
  title={Identifying efficient controls of complex interaction networks using genetic algorithms},
  author={Popescu et al. (2020)},
  year={2020},
  note={arXiv:2007.04853}
}

• arXiv: 2007.04853