93 citations · 347 across the 18 of their papers we have counts for
19 papers
Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems
David García-Soriano, Atsushi Miyauchi
The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most clusters using independ…
Densest Diverse Subgraphs: How to Plan a Successful Cocktail Party with Diversity
Atsushi Miyauchi, Tianyi Chen, Konstantinos Sotiropoulos +1
Dense subgraph discovery methods are routinely used in a variety of applications including the identification of a team of skilled individuals for collaboration from a social netwo…
A Survey on the Densest Subgraph Problem and Its Variants
Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone +1
The Densest Subgraph Problem requires to find, in a given graph, a subset of vertices whose induced subgraph maximizes a measure of density. The problem has received a great deal o…
Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks
Yasushi Kawase, Atsushi Miyauchi, Hanna Sumita
Network analysis has played a key role in knowledge discovery and data mining. In many real-world applications in recent years, we are interested in mining multilayer networks, whe…
A Study on Modularity Density Maximization: Column Generation Acceleration and Computational Complexity Analysis
Issey Sukeda, Atsushi Miyauchi, Akiko Takeda
Community detection is a fundamental network-analysis primitive with a variety of applications in diverse domains. Although the modularity introduced by Newman and Girvan (2004) ha…
Dense and well-connected subgraph detection in dual networks
Tianyi Chen, Francesco Bonchi, David Garcia-Soriano +2
Dense subgraph discovery is a fundamental problem in graph mining with a wide range of applications \cite{gionis2015dense}. Despite a large number of applications ranging from comp…
A Projected Gradient Method for Opinion Optimization with Limited Changes of Susceptibility to Persuasion
Naoki Marumo, Atsushi Miyauchi, Akiko Takeda +1
Many social phenomena are triggered by public opinion that is formed in the process of opinion exchange among individuals. To date, from the engineering point of view, a large body…
Finding Densest -Connected Subgraphs
Francesco Bonchi, David García-Soriano, Atsushi Miyauchi +1
Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph dis…
Online Dense Subgraph Discovery via Blurred-Graph Feedback
Yuko Kuroki, Atsushi Miyauchi, Junya Honda +1
Dense subgraph discovery aims to find a dense component in edge-weighted graphs. This is a fundamental graph-mining task with a variety of applications and thus has received much a…
Hypergraph Clustering Based on PageRank
Yuuki Takai, Atsushi Miyauchi, Masahiro Ikeda +1
A hypergraph is a useful combinatorial object to model ternary or higher-order relations among entities. Clustering hypergraphs is a fundamental task in network analysis. In this s…
Graph Mining Meets Crowdsourcing: Extracting Experts for Answer Aggregation
Yasushi Kawase, Yuko Kuroki, Atsushi Miyauchi
Aggregating responses from crowd workers is a fundamental task in the process of crowdsourcing. In cases where a few experts are overwhelmed by a large number of non-experts, most…
Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback
Yuko Kuroki, Liyuan Xu, Atsushi Miyauchi +2
We study the problem of stochastic combinatorial pure exploration (CPE), where an agent sequentially pulls a set of single arms (a.k.a. a super arm) and tries to find the best supe…
Robust Densest Subgraph Discovery
Atsushi Miyauchi, Akiko Takeda
Dense subgraph discovery is an important primitive in graph mining, which has a wide variety of applications in diverse domains. In the densest subgraph problem, given an undirecte…
Finding Cheeger Cuts in Hypergraphs via Heat Equation
Masahiro Ikeda, Atsushi Miyauchi, Yuuki Takai +1
Cheeger's inequality states that a tightly connected subset can be extracted from a graph using an eigenvector of the normalized Laplacian associated with . More specificall…
The Densest Subgraph Problem with a Convex/Concave Size Function
Yasushi Kawase, Atsushi Miyauchi
In the densest subgraph problem, given an edge-weighted undirected graph , we are asked to find that maximizes the density, i.e., , where …
Additive Approximation Algorithms for Modularity Maximization
Yasushi Kawase, Tomomi Matsui, Atsushi Miyauchi
The modularity is a quality function in community detection, which was introduced by Newman and Girvan (2004). Community detection in graphs is now often conducted through modulari…
Z-score-based modularity for community detection in networks
Atsushi Miyauchi, Yasushi Kawase
Identifying community structure in networks is an issue of particular interest in network science. The modularity introduced by Newman and Girvan [Phys. Rev. E 69, 026113 (2004)] i…
Fractional programming formulation for the vertex coloring problem
Tomomi Matsui, Noriyoshi Sukegawa, Atsushi Miyauchi
We devise a new formulation for the vertex coloring problem. Different from other formulations, decision variables are associated with the pairs of vertices. Consequently, colors w…
Maximizing Barber's bipartite modularity is also hard
Atsushi Miyauchi, Noriyoshi Sukegawa
Modularity introduced by Newman and Girvan [Phys. Rev. E 69, 026113 (2004)] is a quality function for community detection. Numerous methods for modularity maximization have been de…