[FLINK-3925] GraphAlgorithm to filter by maximum degree

• Type: New Feature
• Status: Closed
• Priority: Minor
• Resolution: Implemented
• Affects Version/s: 1.1.0
• Fix Version/s: 1.1.0
• Component/s: Library / Graph Processing
• Assignee: Greg Hogan
• Reporter: Greg Hogan
• Created: 18/May/16 15:27
• Updated: 07/Jun/16 15:00
• Resolved: 07/Jun/16 15:00

Description

Filtering by minimum degree is K-Core which is iterative. Filtering by maximum degree can be performed in constant time by filtering the set of high-degree vertices then doing an anti-join against the original vertex set and two anti-joins against the original edge set.

Two reasons to remove high-degree vertices: 1) they may simply be noise in the input data, and 2) speedup algorithms such as Adamic-Adar and Jaccard Index which run quadratic in the vertex degree.

Issue Links

• links to: GitHub Pull Request #2005