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

Citation Author(s):
Joanna
Raczek
Gdańsk University of Technology
Mateusz
Miotk
University of Gdańsk
Submitted by:
Joanna Raczek
Last updated:
Tue, 12/03/2024 - 04:16
DOI:
10.21227/bjwq-z470
Data Format:
*.csv (zip); R-Data
License:
Creative Commons Attribution
17 Views
Categories:
Reliability
Security
Social Sciences
Keywords:
Certified dominating sets, Social network analysis, Algorithm Complexity; graph theory; optimization
0
0 ratings - Please login to submit your rating.
ACCESS DATASET CITE SHARE/EMBED

Abstract 

Two Approaches to Constructing Certified Dominating Sets in Social Networks: R Script Description

This script implements and analyzes various algorithms for graph processing, focusing on domination problems, including double domination and certified dominating sets.

Script Overview

The 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 Features

  • Tree 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 Components

generate_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:
    1. Resets graph attributes using reset_graph.
    2. Selects nodes iteratively based on their "power" metric until all nodes are dominated.
    3. 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:
    1. Resets graph attributes with basic_reset.
    2. Computes an initial dominating set using greedy_dominating_set.
    3. 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:
    1. Phase 0: Classifies nodes into leaves and supports.
    2. Phase 1: Adjusts node states based on neighbors.
    3. 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.

Results

The 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.
Instructions: 

Certified Dominating Sets: R Script Description

This R script implements and analyzes algorithms for constructing certified dominating sets in graphs. The focus lies on utilizing the ApproxCert algorithm and solving the problem through Integer Linear Programming (ILP).

Script Overview

The script is designed to process graphs in DIMACS `.col` format and compute certified dominating sets using ApproxCert or ILP-based approaches. It supports parallel processing and outputs the results in a CSV file for further analysis.

Key Features

  • Library Management: Automatically installs and loads necessary libraries.
  • Graph Processing: Reads `.col` files and prepares adjacency matrices for analysis.
  • Algorithm Execution: Implements ApproxCert and ILP-based methods for solving the problem.
  • Performance Comparison: Measures execution times and results of the algorithms.
  • Parallel Processing: Utilizes multiple CPU cores for efficient processing.
  • Results Export: Saves execution times and results in `algorithm_results.csv`.

Main Components

certified_ILP(T)

Solves the certified dominating set problem using Integer Linear Programming (ILP). Constructs a mathematical model with the following constraints:

  • Each node and its neighbors must be dominated.
  • Constraints ensure double domination, accounting for redundancy.

The ILP model is solved using the `ompr` and `ROI` packages with the GLPK solver. The function returns the size of the certified dominating set.

approxCer(G)

Implements the ApproxCert algorithm to compute an approximate certified dominating set. The algorithm proceeds as follows:

  1. Initializes the graph by resetting all node attributes.
  2. Iteratively selects nodes with the highest "power" to include in the dominating set.
  3. Minimizes the dominating set by removing redundant nodes while maintaining domination.

The function returns the size of the certified dominating set.

reset(G)

Prepares the graph for ApproxCert execution by setting initial attributes:

  • Status (`sta`): Identifies leaves (`L`) and support nodes (`S`).
  • Dominance (`dom`): Tracks the number of dominated neighbors.
  • Power (`pow`): Computes the potential influence of each node.

updateDom(G, y)

Updates domination properties of node y and its neighbors after changes to the dominating set. Ensures consistency of the domination count (`dom`) and undominated neighbors (`out`).

updatePow(G, y)

Recomputes the power (`pow`) of nodes after a node y is added to the dominating set. This function recalculates node influence, ensuring accurate decision-making in ApproxCert.

mat(T)

Converts a graph into an adjacency matrix. Used as a preprocessing step for ILP modeling.

read_col_file(file_path)

Reads a `.col` file in DIMACS format and converts it into an `igraph` object for further processing.

main(folder_path, algorithm, repetitions)

Processes all `.col` files in a specified folder using a given algorithm. Computes results for each file and exports them to `algorithm_results.csv`.

  • Arguments:
    • folder_path: Path to the folder containing `.col` files.
    • algorithm: The algorithm to apply (e.g., approxCer).
    • repetitions: Number of repetitions for each file to average execution time.

Results

The output is saved in `algorithm_results.csv` with the following columns:

  • File: Name of the processed `.col` file.
  • Algorithm_Time: Average execution time (in seconds).
  • Algorithm_Result: Size of the certified dominating set.

Dataset Files

LOGIN TO ACCESS DATASET FILES

 

QUESTIONS?