BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Yusupjan Habibulla

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

ResearcherUnclaimed source record
physics.soc-phcond-mat.dis-nnphysics.data-anArtificial IntelligenceComputational ComplexityData Structures and AlgorithmsDiscrete Mathematicsphysics.comp-ph

Catalog footprint

What is connected

5works
8topics
2close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

5 published item(s)

preprint2020arXiv

Statistical Mechanics of the Directed 2-distance Minimal Dominating Set problem

The directed L-distance minimal dominating set (MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theoretical interest. We only give results for an Erd$\acute{o}$s R$\acute{e}$nyi (ER) random graph and regular random graph, but this work can be extended to any type of networks. We develop spin glass theory to study the directed 2-distance MDS problem. First, we find that the belief propagation algorithm does not converge when the inverse temperature exceeds a threshold on either an ER random network or regular random network. Second, the entropy density of replica symmetric theory has a transition point at a finite inverse temperature on a regular random graph when the node degree exceeds 4 and on an ER random graph when the node degree exceeds 6.6; there is no entropy transition point (or $β=\infty$) in other circumstances. Third, the results of the replica symmetry (RS) theory are in perfect agreement with those of belief propagation (BP) algorithm while the results of the belief propagation decimation (BPD) algorithm are better than those of the greedy heuristic algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Statistical Mechanics of the L-Distance Minimal Dominating Set problem

Statistical mechanics is widely applied to solve hard optimization problem, the optimal strategy related to ground state energy that depends on low temperature. Common thermodynamic process is expected to approach the ground state energy if the temperature is lowered appropriately, but this belief is not always justified when the network contains more long loops in low temperature. Previously we always implement the canonical equilibrium process to predict the low-energy, but it doesn't work in L-distance (L>1) minimal dominating set problem, because the thermodynamical process can not guarantee to find the stable state of the system at the low temperature. Here, we employ energy-clamping strategy of cavity method ( micro canonical equilibrium process ) to predict low-energy and discover that the microcanonical process still find the stable state of given system at low temperature where canonical process work out. We develop Belief Propagation Decimation (BPD) and Greedy algorithm to calculate the L-distance ($2<L<7$) minimal dominating set, we find that the BPD algorithm results outperform the Greedy algorithm. We have witnessed the emergence of negative $β$ with different mean energy on different L-distance. The free energy has a discontinuous phase transition at $β= 0$. We predict the ground state energy by microcanonical cavity method, overcoming the limitation of canonical cavity method.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Statistical Mechanics of the Minimum Dominating Set Problem

The minimum dominating set problem has wide applications in network science and related fields. It consists of assembling a node set of global minimum size such that any node of the network is either in this set or is adjacent to at least one node of this set. Although this is a difficult optimization problem in general, we show it can be exactly solved by a generalized leaf-removal process if the network contains no core. If the network has an extensive core, we estimate the size of minimum dominating sets by a mean-field theory and implement a belief-propagation algorithm to obtain near-optimal solutions. Our algorithms also perform well on real-world network instances.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation

A minimum dominating set for a digraph (directed graph) is a smallest set of vertices such that each vertex either belongs to this set or has at least one parent vertex in this set. We solve this hard combinatorial optimization problem approximately by a local algorithm of generalized leaf removal and by a message-passing algorithm of belief propagation. These algorithms can construct near-optimal dominating sets or even exact minimum dominating sets for random digraphs and also for real-world digraph instances. We further develop a core percolation theory and a replica-symmetric spin glass theory for this problem. Our algorithmic and theoretical results may facilitate applications of dominating sets to various network problems involving directed interactions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

CCCP Algorithms to Minimize the Bethe free energy of 3-SAT Problem

The k-sat problem is a prototypical constraint satisfaction problem. There are many algorithms to study k-sat problem, BP algorithm is famous one of them. But BP algorithm does not converge when $α$(constraint density)is bigger than some threshold value. In this paper we use CCCP (Concave Convex Procedure) algorithm to study 3-sat problem and we get better results than BP algorithm that CCCP algorithm still converges when BP algorithm does not converge. Our work almost builds on recent results by Yuille \cite{Yuille2002} who apply the CCCP algorithm to Bethe and Kikuchi free energies and obtained two algorithms on 2D and 3D spin glasses. Our implementation of CCCP algorithm on 3-sat problem is some different from his implementation and we have some different views about CCCP algorithm's some properties. Some difference of these maybe because of CCCP algorithm have different properties and implementation process on different problem and some others of these are related to the CCCP algorithm itself. Our work indicates that CCCP algorithm has more learning and inference applications.

0 citations0 reviewsNo code linkedOpen access