Algorithmic aspects of homophyly of networks

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

Peng Zhang, Angsheng Li

Publication date: 8 October 2015

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Multiterminal Cuts
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Dynamic models of segregation†
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Network Flow and Testing Graph Connectivity
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Finding k Cuts within Twice the Optimal
• Approximation algorithms for classification problems with pairwise relationships
• The small-community phenomenon in networks
• 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
• Community structures in classical network models

Cited In (23)

• Parameterized algorithms for the happy set problem
• Title not available (Why is that?)
• 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
• 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
• Approximation algorithms for vertex happiness
• Happy set problem on subclasses of co-comparability graphs
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
• Approximation and Hardness Results for the Max k-Uncut 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
• Complexity and approximability of the happy set problem
• Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
• New algorithms for a simple measure of network partitioning
• Happy set problem on subclasses of co-comparability graphs
• Lower bounds for the happy coloring problems
• 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)