Algorithmic aspects of homophyly of networks

DOI10.1016/j.tcs.2015.06.003zbMath1330.68127arXiv1207.0316OpenAlexW1913738529MaRDI QIDQ501003

Peng Zhang, Ang Sheng Li

Publication date: 8 October 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.0316

zbMATH Keywords

social networksapproximation algorithmshomophylymaximum happy edgesmaximum happy vertices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items

A simple and effective algorithm for the maximum happy vertices problem ⋮ Approximation and hardness results for the max \(k\)-uncut problem ⋮ Finding happiness: an analysis of the maximum happy vertices problem ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems ⋮ Complexity and approximability of the happy set problem ⋮ Parameterized complexity of happy coloring problems ⋮ Approximation and Hardness Results for the Max k-Uncut Problem ⋮ On \(d\)-stable locally checkable problems parameterized by mim-width ⋮ New algorithms for a simple measure of network partitioning ⋮ Improved approximation algorithms for the maximum happy vertices and edges problems ⋮ Parameterized algorithms for the happy set problem ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ Graph classes and approximability of the happy set problem ⋮ Tackling the maximum happy vertices problem in large networks ⋮ The maximum happy induced subgraph problem: bounds and algorithms ⋮ New algorithms for a simple measure of network partitioning ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Lower bounds for the happy coloring problems ⋮ Linear Time Algorithms for Happy Vertex Coloring Problems for Trees ⋮ Approximation algorithms for vertex happiness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• An improved approximation algorithm of MULTIWAY CUT.
• Greedy splitting algorithms for approximating multiway partition problems
• Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem
• Rounding algorithms for a geometric embedding of minimum multiway cut
• The small-community phenomenon in networks
• Community Structures in Classical Network Models
• Dynamic models of segregation†
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Approximation algorithms for classification problems with pairwise relationships
• Network Flow and Testing Graph Connectivity
• The Complexity of Multiterminal Cuts
• Finding k Cuts within Twice the Optimal