Related Experiment Video
Updated: Mar 19, 2026
05:12
ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data
Published on: January 16, 2019
12.0K
Linear Time Vertex Partitioning on Massive Graphs
Peter Mell1, Richard Harang2, Assane Gueye3
1National Institute of Standards and Technology, USA.
International Journal of Computer Science (Rabat)
|June 24, 2016
Summary
We present a linear-time algorithm for vertex partitioning in massive graphs, improving upon existing methods for large-scale network analysis. This scalable solution efficiently handles graphs with millions of nodes, crucial for understanding complex network structures.
Area of Science:
- Graph Theory
- Network Science
- Computer Science
Background:
- Vertex partitioning to minimize largest component size is NP-complete.
- Existing heuristics struggle with massive graphs due to high time complexity.
Purpose of the Study:
- Develop a scalable algorithm for vertex partitioning on graphs with tens of millions of nodes.
- Reduce the time complexity of iterative node removal heuristics.
Main Methods:
- Employed a heuristic of iteratively removing the node of largest degree.
- Developed a linear-time solution using an array indexed by node degree and hash tables.
- Analyzed time and memory complexity, demonstrating linear scalability.
Main Results:
- Achieved linear time complexity (O(n)) for the vertex partitioning heuristic.
- Demonstrated linear memory usage, contrary to expectations for improved time complexity.
- Empirically validated scalability on random graphs up to 15,000 nodes.
- Successfully applied the method to a 34-million-node graph of internet router connectivity.
Conclusions:
- The developed linear-time algorithm provides a tractable solution for vertex partitioning on massive graphs.
- This approach significantly advances the analysis of large-scale networks, such as internet topology.
Related Concept Videos
01:10Vector Algebra: Graphical Method
18.5K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
18.5K
01:30Graphs of Functions
463
Graphs of functions provide a visual representation of how output values change in response to varying inputs. Each point on the graph corresponds to an ordered pair, where the x-coordinate (independent variable) determines the horizontal position and the y-coordinate (dependent variable) determines the vertical position. Linear functions like y = x give a straight line, indicating a constant rate of change.Nonlinear functions display more complex behaviors. Even power functions generate...
463
01:14Extraction: Partition and Distribution Coefficients
5.4K
The distribution law or Nernst's distribution law is the law that governs the distribution of a solute between two immiscible solvents. This law, also known as the partition law, states that if a solute is added to the mixture of two immiscible solvents at a constant temperature, the solute is distributed between the two solvents in such a way that the ratio of solute concentrations in the solvents remains constant at equilibrium.
For extracting a solute from an aqueous phase into an...
For extracting a solute from an aqueous phase into an...
5.4K
01:30Graphs of Equations in Two Variables
355
An equation with two variables, typically written in the form y = f(x) or Ax + By = C, describes a relationship between quantities represented by x and y. Each solution to such an equation is an ordered pair (x, y) that satisfies the equation when substituted. These pairs can be represented graphically to understand the variables' relationship visually.A common technique for constructing the graph of a two-variable equation is to create a value table. Begin by choosing several values for the...
355
01:19Survival Tree
463
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
Building a Survival Tree
Constructing a...
Building a Survival Tree
Constructing a...
463
01:24Sequence Networks of Rotating Machines
517
A Y-connected synchronous generator, grounded through a neutral impedance, is designed to produce balanced internal phase voltages with only positive-sequence components. The generator's sequence networks include a source voltage that is exclusively in the positive-sequence network. The sequence components of line-to-ground voltages at the generator terminals illustrate this configuration.
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
517