Data Set and Source Files of Two Approaches to Constructing Certified Dominating Sets in Social Networks

Two Approaches to Constructing Certified Dominating Sets in Social Networks: R Script DescriptionThis script implements and analyzes various algorithms for graph processing, focusing on domination problems, including double domination and certified dominating sets.Script OverviewThe script generates tree graphs, calculates certified dominating sets using ApproxCert and other algorithms, and evaluates their performance in terms of execution time and results. Results are saved in a CSV file for further analysis.Key FeaturesTree Generation: Creates random tree graphs with specified numbers of nodes.Domination Algorithms: Implements ApproxCert, Greedy Dominating Set, and Double Domination algorithms.Performance Evaluation: Measures execution times and results for different algorithms.Validation: Ensures computed sets are valid dominating sets.Results Export: Saves detailed results to a CSV file for further analysis.Main Componentsgenerate_tree(count)Generates a random tree graph with a specified number of nodes.Input: count - Number of nodes in the tree.Output: An `igraph` object representing the tree.Details: Ensures the tree is undirected and connected.greedy_dominating_set(G)Computes a dominating set using a greedy algorithm by iteratively selecting the vertex with the highest degree.Input: G - Input graph.Output: Graph with updated node attributes indicating the dominating set.approximate_cer(G)Implements the ApproxCert algorithm to calculate an approximate certified dominating set.Steps:Resets graph attributes using reset_graph.Selects nodes iteratively based on their "power" metric until all nodes are dominated.Minimizes the dominating set by removing redundant nodes.Output: Size of the certified dominating set.double_domination(T)Computes a double dominating set using a combination of greedy and CFDS (Certified From Dominating Set) approaches.Steps:Resets graph attributes with basic_reset.Computes an initial dominating set using greedy_dominating_set.Refines the dominating set using construct_CFDS.Output: A list containing the size of the double dominating set and execution times of the sub-steps.linear_Trees(T)Processes a tree graph in phases to determine its minimal dominating set using linear time algorithms.Phases:Phase 0: Classifies nodes into leaves and supports.Phase 1: Adjusts node states based on neighbors.Phase 22: Further refines node states to ensure domination.Output: Count of nodes in the minimal dominating set.test_algorithms(start_n, end_n, step_n, output_file)Tests the implemented algorithms for graphs of various sizes and records the results.Inputs:start_n - Initial number of nodes.end_n - Final number of nodes.step_n - Step size for node count increment.output_file - Path to save the results.Output: A CSV file containing:Graph size.Results of `linear_Trees` and `approximate_cer`.Execution times of different algorithms.is_dominating(G, D)Validates whether a given set D is a dominating set for graph G.Output: TRUE if all nodes are dominated, FALSE otherwise.ResultsThe results of the experiments are saved in a CSV file with the following columns:n: Number of nodes in the graph.lTrees: Result from the linear_Trees algorithm.approx: Result from the approximate_cer algorithm.approx_double_with_greedy: Size of the double dominating set.Execution times: Times recorded for each algorithm and step.