Algorithmic aspects of homophyly of networks

DOI10.1016/J.TCS.2015.06.003MaRDI QIDQ501003zbMATH OpenOpenAlexFDO

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)

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

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)