Source author record

Atsushi Miyauchi

Atsushi Miyauchi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Social and Information Networks Data Structures and Algorithms physics.soc-ph Computational Complexity Machine Learning Quantitative Methods

Catalog footprint

What is connected

5works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Online Dense Subgraph Discovery via Blurred-Graph Feedback

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 attention recently. Although most existing methods assume that each individual edge weight is easily obtained, such an assumption is not necessarily valid in practice. In this paper, we introduce a novel learning problem for dense subgraph discovery in which a learner queries edge subsets rather than only single edges and observes a noisy sum of edge weights in a queried subset. For this problem, we first propose a polynomial-time algorithm that obtains a nearly-optimal solution with high probability. Moreover, to deal with large-sized graphs, we design a more scalable algorithm with a theoretical guarantee. Computational experiments using real-world graphs demonstrate the effectiveness of our algorithms.

preprint2016arXiv

pSpatiocyte: A Parallel Stochastic Method for Particle Reaction-Diffusion Systems

Computational systems biology has provided plenty of insights into cell biology. Early on, the focus was on reaction networks between molecular species. Spatial distribution only began to be considered mostly within the last decade. However, calculations were restricted to small systems because of tremendously high computational workloads. To date, application to the cell of typical size with molecular resolution is still far from realization. In this article, we present a new parallel stochastic method for particle reaction-diffusion systems. The program called pSpatiocyte was created bearing in mind reaction networks in biological cells operating in crowded intracellular environments as the primary simulation target. pSpatiocyte employs unique discretization and parallelization algorithms based on a hexagonal close-packed lattice for efficient execution particularly on large distributed memory parallel computers. For two-level parallelization, we introduced isolated subdomain and tri-stage lockstep communication for process-level, and voxel-locking techniques for thread-level. We performed a series of parallel runs on RIKEN's K computer. For a fine lattice that had relatively low occupancy, pSpatiocyte achieved 7686 times speedup with 663552 cores relative to 64 cores from the viewpoint of strong scaling and exhibited 74\% parallel efficiency. As for weak scaling, efficiencies at least 60% were observed up to 663552 cores. In addition to computational performance, diffusion and reaction rates were validated by theory and another well-validated program and had good agreement. Lastly, as a preliminary example of real-world applications, we present a calculation of the MAPK model, a typical reaction network motif in cell signaling pathways.

preprint2015arXiv

Z-score-based modularity for community detection in networks

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)] is the most popular quality function for community detection in networks. In this study, we identify a problem in the concept of modularity and suggest a solution to overcome this problem. Specifically, we obtain a new quality function for community detection. We refer to the function as Z-modularity because it measures the Z-score of a given division with respect to the fraction of the number of edges within communities. Our theoretical analysis shows that Z-modularity mitigates the resolution limit of the original modularity in certain cases. Computational experiments using both artificial networks and well-known real-world networks demonstrate the validity and reliability of the proposed quality function.

preprint2014arXiv

Fractional programming formulation for the vertex coloring problem

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 will be distinguishable. Although the objective function is fractional, it can be replaced by a piece-wise linear convex function. Numerical experiments show that our formulation has significantly good performance for dense graphs.

preprint2013arXiv

Maximizing Barber's bipartite modularity is also hard

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 developed so far. In 2007, Barber [Phys. Rev. E 76, 066102 (2007)] introduced a variant of modularity called bipartite modularity which is appropriate for bipartite networks. Although maximizing the standard modularity is known to be NP-hard, the computational complexity of maximizing bipartite modularity has yet to be revealed. In this study, we prove that maximizing bipartite modularity is also NP-hard. More specifically, we show the NP-completeness of its decision version by constructing a reduction from a classical partitioning problem.