Algorithmic aspects of homophyly of networks

DOI10.1016/J.TCS.2015.06.003zbMATH Open1330.68127OpenAlexW1913738529MaRDI QIDQ501003FDOQ501003

Authors Peng Zhang, Angsheng 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) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Abstract: We investigate the algorithmic problems of the {it homophyly phenomenon} in networks. Given an undirected graph $G=(V,E)$ and a vertex coloring $ccolonVightarrow1,2,\mathrm{...},k$ of $G$, we say that a vertex $vinV$ is {it happy} if $v$ shares the same color with all its neighbors, and {it unhappy}, otherwise, and that an edge $einE$ is {it happy}, if its two endpoints have the same color, and {it unhappy}, otherwise. Supposing $c$ is a {it partial vertex coloring} of $G$, we define the Maximum Happy Vertices problem (MHV, for short) as to color all the remaining vertices such that the number of happy vertices is maximized, and the Maximum Happy Edges problem (MHE, for short) as to color all the remaining vertices such that the number of happy edges is maximized. Let $k$ be the number of colors allowed in the problems. We show that both MHV and MHE can be solved in polynomial time if $k=2$, and that both MHV and MHE are NP-hard if $kgeq3$. We devise a $max1/k,Omega(Delt{a}^{-3})$-approximation algorithm for the MHV problem, where $Delta$ is the maximum degree of vertices in the input graph, and a 1/2-approximation algorithm for the MHE problem. This is the first theoretical progress of these two natural and fundamental new problems.

Recommendations

• Parameterized complexity of happy coloring problems
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Kernelization for maximum happy vertices problem
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees

Cites work

• scientific article; zbMATH DE number 3860199 (Why is no real title available?)
• scientific article; zbMATH DE number 1332666 (Why is no real title available?)
• An improved approximation algorithm of MULTIWAY CUT.
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Community structures in classical network models
• Dynamic models of segregation†
• Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem
• Finding k Cuts within Twice the Optimal
• Greedy splitting algorithms for approximating multiway partition problems
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Network Flow and Testing Graph Connectivity
• Networks, crowds and markets. Reasoning about a highly connected world.
• The Complexity of Multiterminal Cuts
• The small-community phenomenon in networks

Cited in

(23)

• Finding happiness: an analysis of the maximum happy vertices problem
• A simple and effective algorithm for the maximum happy vertices problem
• Approximation and hardness results for the max \(k\)-uncut problem
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Approximation and hardness results for the max \(k\)-uncut problem
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
• Tackling the maximum happy vertices problem in large networks
• The maximum happy induced subgraph problem: bounds and algorithms
• On \(d\)-stable locally checkable problems parameterized by mim-width
• Parameterized algorithms for the happy set problem
• Complexity and approximability of the happy set problem
• Happy set problem on subclasses of co-comparability graphs
• Kernelization for maximum happy vertices problem
• Happy set problem on subclasses of co-comparability graphs
• Parameterized complexity of happy coloring problems
• New algorithms for a simple measure of network partitioning
• Graph classes and approximability of the happy set problem
• 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
• Approximation algorithms for vertex happiness
• scientific article; zbMATH DE number 6304438 (Why is no real title available?)
• Improved approximation algorithms for the maximum happy vertices and edges problems

This page was built for publication: Algorithmic aspects of homophyly of networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501003)