Glossario IA
Il dizionario completo dell'Intelligenza Artificiale
Graph Partitioning
Algorithmic process aimed at dividing a graph into several disjoint subsets of nodes while minimizing the number of edges between these partitions, thus optimizing intra-partition cohesion and inter-partition separation.
Spectral Method
Partitioning approach based on the analysis of the eigenvectors of the graph's Laplacian, using the smallest eigenvalues to identify minimal cuts and natural community structures.
Minimum Cut
Fundamental problem consisting of finding a minimal set of edges whose removal disconnects the graph into at least two connected components, often used as an optimization criterion in partitioning.
METIS Algorithm
Suite of high-performance multilevel algorithms for graph and mesh partitioning, combining coarsening, initial partitioning, and refinement to obtain high-quality solutions in linear time.
Multilevel Partitioning
Hierarchical strategy that progressively coarsens the graph to reduce its size, partitions the simplified graph, and then uncoarsens and iteratively refines the partition to reach the original graph.
Graph Coarsening
Phase of multilevel partitioning where vertices and edges are merged to create a smaller graph while preserving essential structural properties to facilitate partitioning.
Partition Refinement
Iterative process of local improvement of an existing partition by selectively moving vertices between adjacent partitions to reduce the cut cost while respecting balance constraints.
Balanced Partitioning
Partitioning constraint requiring that each partition contains approximately the same number or weight of vertices, essential for parallel applications and load balancing.
Modularity optimization
Quality criterion measuring the density of intra-community connections compared to a null model, used to evaluate and guide community detection algorithms in graphs.
k-way partitioning
Generalization of binary partitioning aiming to divide a graph directly into k partitions, simultaneously optimizing interactions between all pairs of partitions.
Vertex cut
Alternative to edge cut where vertices can be replicated between partitions, minimizing the total number of duplicated vertices rather than the number of inter-partition edges.
Hypergraph partitioning
Extension of graph partitioning to hypergraphs where hyperedges can connect more than two vertices, applied notably in VLSI circuit design and data partitioning.
Load balancing
Partitioning objective ensuring uniform distribution of work or resources between partitions, crucial for the performance of parallel and distributed systems.
Fiduccia-Mattheyses algorithm
Linear variant of the Kernighan-Lin algorithm using bucket data structures to accelerate gain calculation, becoming the reference for VLSI circuit partitioning.
Partition quality
Set of metrics evaluating a partition including cut ratio, weight balance, partition diameter, and intra-partition connectivity, allowing comparison of different solutions.