BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Valmir C. Barbosa

Valmir C. Barbosa contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
cond-mat.stat-mechNetworking and Internet ArchitectureNeurons and CognitionPopulations and EvolutionNeural and Evolutionary ComputingArtificial IntelligenceData Structures and AlgorithmsDiscrete MathematicsDistributed, Parallel, and Cluster Computingmath.COmath.PRnlin.CGOperating SystemsSocial and Information Networks

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
20works
0followers
14topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

20 published item(s)

preprint2021arXiv

Integrated optimization of heterogeneous-network management and the elusive role of macrocells

We consider heterogeneous wireless networks in the physical interference model and introduce a new formulation of the mixed-integer nonlinear programming problem that addresses base-station activation and many-to-many associations while minimizing power consumption. We also introduce HetNetGA, a genetic algorithm that can tackle the problem without any approximations. Though unsuitable for practical deployment, HetNetGA enables the investigation of such networks' true possibilities. Results for scenarios involving both macrocells and picocells often align with what is expected, but sometimes are unexpected and essentially point to the need to better understand the role of macrocells in helping provide capacity while remaining energetically advantageous.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Interspecies evolutionary dynamics mediated by public goods in bacterial quorum sensing

Bacterial quorum sensing is the communication that takes place between bacteria as they secrete certain molecules into the intercellular medium that later get absorbed by the secreting cells themselves and by others. Depending on cell density, this uptake has the potential to alter gene expression and thereby affect global properties of the community. We consider the case of multiple bacterial species coexisting, referring to each one of them as a genotype and adopting the usual denomination of the molecules they collectively secrete as public goods. A crucial problem in this setting is characterizing the coevolution of genotypes as some of them secrete public goods (and pay the associated metabolic costs) while others do not but may nevertheless benefit from the available public goods. We introduce a network model to describe genotype interaction and evolution when genotype fitness depends on the production and uptake of public goods. The model comprises a random graph to summarize the possible evolutionary pathways the genotypes may take as they interact genetically with one another, and a system of coupled differential equations to characterize the behavior of genotype abundance in time. We study some simple variations of the model analytically and more complex variations computationally. Our results point to a simple trade-off affecting the long-term survival of those genotypes that do produce public goods. This trade-off involves, on the producer side, the impact of producing and that of absorbing the public good. On the non-producer side, it involves the impact of absorbing the public good as well, now compounded by the molecular compatibility between the producer and the non-producer. Depending on how these factors turn out, producers may or may not survive.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Scheduling wireless links in the physical interference model by fractional edge coloring

We consider the problem of scheduling the links of wireless mesh networks for capacity maximization in the physical interference model. We represent such a network by an undirected graph $G$, with vertices standing for network nodes and edges for links. We define network capacity to be $1/χ&#39;^*_\mathrm{phys}(G)$, where $χ&#39;^*_\mathrm{phys}(G)$ is a novel edge-chromatic indicator of $G$, one that modifies the notion of $G$&#39;s fractional chromatic index. This index asks that the edges of $G$ be covered by matchings in a certain optimal way. The new indicator does the same, but requires additionally that the matchings used be all feasible in the sense of the physical interference model. Sometimes the resulting optimal covering of $G$&#39;s edge set by feasible matchings is simply a partition of the edge set. In such cases, the index $χ&#39;^*_\mathrm{phys}(G)$ becomes the particular case that we denote by $χ&#39;_\mathrm{phys}(G)$, a similar modification of $G$&#39;s well-known chromatic index. We formulate the exact computation of $χ&#39;^*_\mathrm{phys}(G)$ as a linear programming problem, which we solve for an extensive collection of random geometric graphs used to instantiate networks in the physical interference model. We have found that, depending on node density (number of nodes per unit deployment area), often $G$ is such that $χ&#39;^*_\mathrm{phys}(G)<χ&#39;_\mathrm{phys}(G)$. This bespeaks the possibility of increased network capacity by virtue of simply defining it so that edges are colored in the fractional, rather than the integer, sense.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Co-evolution of the mitotic and meiotic modes of eukaryotic cellular division

The genetic material of a eukaryotic cell comprises both nuclear DNA (ncDNA) and mitochondrial DNA (mtDNA). These differ markedly in several aspects but nevertheless must encode proteins that are compatible with one another. Here we introduce a network model of the hypothetical co-evolution of the two most common modes of cellular division for reproduction: by mitosis (supporting asexual reproduction) and by meiosis (supporting sexual reproduction). Our model is based on a random hypergraph, with two nodes for each possible genotype, each encompassing both ncDNA and mtDNA. One of the nodes is necessarily generated by mitosis occurring at a parent genotype, the other by meiosis occurring at two parent genotypes. A genotype&#39;s fitness depends on the compatibility of its ncDNA and mtDNA. The model has two probability parameters, $p$ and $r$, the former accounting for the diversification of ncDNA during meiosis, the latter for the diversification of mtDNA accompanying both meiosis and mitosis. Another parameter, $λ$, is used to regulate the relative rate at which mitosis- and meiosis-generated genotypes are produced. We have found that, even though $p$ and $r$ do affect the existence of evolutionary pathways in the network, the crucial parameter regulating the coexistence of the two modes of cellular division is $λ$. Depending on genotype size, $λ$ can be valued so that either mode of cellular division prevails. Our study is closely related to a recent hypothesis that views the appearance of cellular division by meiosis, as opposed to division by mitosis, as an evolutionary strategy for boosting ncDNA diversification to keep up with that of mtDNA. Our results indicate that this may well have been the case, thus lending support to the first hypothesis in the field to take into account the role of such ubiquitous and essential organelles as mitochondria.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Local symmetry in random graphs

Quite often real-world networks can be thought of as being symmetric, in the abstract sense that vertices can be found to have similar or equivalent structural roles. However, traditional measures of symmetry in graphs are based on their automorphism groups, which do not account for the similarity of local structures. We introduce the concept of local symmetry, which reflects the structural equivalence of the vertices&#39; egonets. We study the emergence of asymmetry in the Erdős-Rényi random graph model and identify regimes of both asymptotic local symmetry and asymptotic local asymmetry. We find that local symmetry persists at least to an average degree of $n^{1/3}$ and local asymmetry emerges at an average degree not greater than $n^{1/2}$, which are regimes of much larger average degree than for traditional, global asymmetry.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Further insights into the interareal connectivity of a cortical network

Over the past years, network science has proven invaluable as a means to better understand many of the processes taking place in the brain. Recently, interareal connectivity data of the macaque cortex was made available with great richness of detail. We explore new aspects of this dataset, such as a correlation between connection weights and cortical hierarchy. We also look at the link-community structure that emerges from the data to uncover the major communication pathways in the network, and moreover investigate its reciprocal connections, showing that they share similar properties.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Network algorithmics and the emergence of synchronization in cortical models

When brain signals are recorded in an electroencephalogram or some similar large-scale record of brain activity, oscillatory patterns are typically observed that are thought to reflect the aggregate electrical activity of the underlying neuronal ensemble. Although it now seems that such patterns participate in feedback loops both temporally with the neurons&#39; spikes and spatially with other brain regions, the mechanisms that might explain the existence of such loops have remained essentially unknown. Here we present a theoretical study of these issues on a cortical model we introduced earlier [Nathan A, Barbosa VC (2010) Network algorithmics and the emergence of the cortical synaptic-weight distribution. Phys Rev E 81: 021916]. We start with the definition of two synchronization measures that aim to capture the synchronization possibilities offered by the model regarding both the overall spiking activity of the neurons and the spiking activity that causes the immediate firing of the postsynaptic neurons. We present computational results on our cortical model, on a model that is random in the Erdős-Rényi sense, and on a structurally deterministic model. We have found that the algorithmic component underlying our cortical model ultimately provides, through the two synchronization measures, a strong quantitative basis for the emergence of both types of synchronization in all cases. This, in turn, may explain the rise both of temporal feedback loops in the neurons&#39; combined electrical activity and of spatial feedback loops as brain regions that are spatially separated engage in rhythmic behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Local heuristic for the refinement of multi-path routing in wireless mesh networks

We consider wireless mesh networks and the problem of routing end-to-end traffic over multiple paths for the same origin-destination pair with minimal interference. We introduce a heuristic for path determination with two distinguishing characteristics. First, it works by refining an extant set of paths, determined previously by a single- or multi-path routing algorithm. Second, it is totally local, in the sense that it can be run by each of the origins on information that is available no farther than the node&#39;s immediate neighborhood. We have conducted extensive computational experiments with the new heuristic, using AODV and OLSR, as well as their multi-path variants, as underlying routing methods. For two different CSMA settings (as implemented by 802.11) and one TDMA setting running a path-oriented link scheduling algorithm, we have demonstrated that the new heuristic is capable of improving the average throughput network-wide. When working from the paths generated by the multi-path routing algorithms, the heuristic is also capable to provide a more evenly distributed traffic pattern.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The conduciveness of CA-rule graphs

Given two subsets A and B of nodes in a directed graph, the conduciveness of the graph from A to B is the ratio representing how many of the edges outgoing from nodes in A are incoming to nodes in B. When the graph&#39;s nodes stand for the possible solutions to certain problems of combinatorial optimization, choosing its edges appropriately has been shown to lead to conduciveness properties that provide useful insight into the performance of algorithms to solve those problems. Here we study the conduciveness of CA-rule graphs, that is, graphs whose node set is the set of all CA rules given a cell&#39;s number of possible states and neighborhood size. We consider several different edge sets interconnecting these nodes, both deterministic and random ones, and derive analytical expressions for the resulting graph&#39;s conduciveness toward rules having a fixed number of non-quiescent entries. We demonstrate that one of the random edge sets, characterized by allowing nodes to be sparsely interconnected across any Hamming distance between the corresponding rules, has the potential of providing reasonable conduciveness toward the desired rules. We conjecture that this may lie at the bottom of the best strategies known to date for discovering complex rules to solve specific problems, all of an evolutionary nature.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A study of the edge-switching Markov-chain method for the generation of random graphs

We study the problem of generating connected random graphs with no self-loops or multiple edges and that, in addition, have a given degree sequence. The generation method we focus on is the edge-switching Markov-chain method, whose functioning depends on a parameter w related to the method&#39;s core operation of an edge switch. We analyze two existing heuristics for adjusting w during the generation of a graph and show that they result in a Markov chain whose stationary distribution is uniform, thus ensuring that generation occurs uniformly at random. We also introduce a novel w-adjusting heuristic which, even though it does not always lead to a Markov chain, is still guaranteed to converge to the uniform distribution under relatively mild conditions. We report on extensive computer experiments comparing the three heuristics&#39; performance at generating random graphs whose node degrees are distributed as power laws.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Evolved preambles for MAX-SAT heuristics

MAX-SAT heuristics normally operate from random initial truth assignments to the variables. We consider the use of what we call preambles, which are sequences of variables with corresponding single-variable assignment actions intended to be used to determine a more suitable initial truth assignment for a given problem instance and a given heuristic. For a number of well established MAX-SAT heuristics and benchmark instances, we demonstrate that preambles can be evolved by a genetic algorithm such that the heuristics are outperformed in a significant fraction of the cases.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quasispecies dynamics with network constraints

A quasispecies is a set of interrelated genotypes that have reached a situation of equilibrium while evolving according to the usual Darwinian principles of selection and mutation. Quasispecies studies invariably assume that it is possible for any genotype to mutate into any other, but recent finds indicate that this assumption is not necessarily true. Here we revisit the traditional quasispecies theory by adopting a network structure to constrain the occurrence of mutations. Such structure is governed by a random-graph model, whose single parameter (a probability p) controls both the graph&#39;s density and the dynamics of mutation. We contribute two further modifications to the theory, one to account for the fact that different loci in a genotype may be differently susceptible to the occurrence of mutations, the other to allow for a more plausible description of the transition from adaptation to degeneracy of the quasispecies as p is increased. We give analytical and simulation results for the usual case of binary genotypes, assuming the fitness landscape in which a genotype&#39;s fitness decays exponentially with its Hamming distance to the wild type. These results support the theory&#39;s assertions regarding the adaptation of the quasispecies to the fitness landscape and also its possible demise as a function of p.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Scheduling links for heavy traffic on interfering routes in wireless mesh networks

We consider wireless mesh networks and the problem of scheduling the links of a given set of routes under the assumption of a heavy-traffic pattern. We assume some TDMA protocol provides a background of synchronized time slots and seek to schedule the routes&#39; links to maximize the number of packets that get delivered to their destinations per time slot. Our approach is to construct an undirected graph G and to heuristically obtain node multicolorings for G that can be turned into efficient link schedules. In G each node represents a link to be scheduled and the edges are set up to represent every possible interference for any given set of interference assumptions. We present two multicoloring-based heuristics and study their performance through extensive simulations. One of the two heuristics is based on relaxing the notion of a node multicoloring by dynamically exploiting the availability of communication opportunities that would otherwise be wasted. We have found that, as a consequence, its performance is significantly superior to the other&#39;s.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Early appraisal of the fixation probability in directed networks

In evolutionary dynamics, the probability that a mutation spreads through the whole population, having arisen in a single individual, is known as the fixation probability. In general, it is not possible to find the fixation probability analytically given the mutant&#39;s fitness and the topological constraints that govern the spread of the mutation, so one resorts to simulations instead. Depending on the topology in use, a great number of evolutionary steps may be needed in each of the simulation events, particularly in those that end with the population containing mutants only. We introduce two techniques to accelerate the determination of the fixation probability. The first one skips all evolutionary steps in which the number of mutants does not change and thereby reduces the number of steps per simulation event considerably. This technique is computationally advantageous for some of the so-called layered networks. The second technique, which is not restricted to layered networks, consists of aborting any simulation event in which the number of mutants has grown beyond a certain threshold value, and counting that event as having led to a total spread of the mutation. For large populations, and regardless of the network&#39;s topology, we demonstrate, both analytically and by means of simulations, that using a threshold of about 100 mutants leads to an estimate of the fixation probability that deviates in no significant way from that obtained from the full-fledged simulations. We have observed speedups of two orders of magnitude for layered networks with 10000 nodes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Network algorithmics and the emergence of information integration in cortical models

An information-theoretic framework known as integrated information theory (IIT) has been introduced recently for the study of the emergence of consciousness in the brain [D. Balduzzi and G. Tononi, PLoS Comput. Biol. 4, e1000091 (2008)]. IIT purports that this phenomenon is to be equated with the generation of information by the brain surpassing the information which the brain&#39;s constituents already generate independently of one another. IIT is not fully plausible in its modeling assumptions, nor is it testable due to severe combinatorial growth embedded in its key definitions. Here we introduce an alternative to IIT which, while inspired in similar information-theoretic principles, seeks to address some of IIT&#39;s shortcomings to some extent. Our alternative framework uses the same network-algorithmic cortical model we introduced earlier [A. Nathan and V. C. Barbosa, Phys. Rev. E 81, 021916 (2010)] and, to allow for somewhat improved testability relative to IIT, adopts the well-known notions of information gain and total correlation applied to a set of variables representing the reachability of neurons by messages in the model&#39;s dynamics. We argue that these two quantities relate to each other in such a way that can be used to quantify the system&#39;s efficiency in generating information beyond that which does not depend on integration, and give computational results on our cortical model and on variants thereof that are either structurally random in the sense of an Erdos-Renyi random directed graph or structurally deterministic. We have found that our cortical model stands out with respect to the others in the sense that many of its instances are capable of integrating information more efficiently than most of those others&#39; instances.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Network conduciveness with application to the graph-coloring and independent-set optimization transitions

We introduce the notion of a network&#39;s conduciveness, a probabilistically interpretable measure of how the network&#39;s structure allows it to be conducive to roaming agents, in certain conditions, from one portion of the network to another. We exemplify its use through an application to the two problems in combinatorial optimization that, given an undirected graph, ask that its so-called chromatic and independence numbers be found. Though NP-hard, when solved on sequences of expanding random graphs there appear marked transitions at which optimal solutions can be obtained substantially more easily than right before them. We demonstrate that these phenomena can be understood by resorting to the network that represents the solution space of the problems for each graph and examining its conduciveness between the non-optimal solutions and the optimal ones. At the said transitions, this network becomes strikingly more conducive in the direction of the optimal solutions than it was just before them, while at the same time becoming less conducive in the opposite direction. We believe that, besides becoming useful also in other areas in which network theory has a role to play, network conduciveness may become instrumental in helping clarify further issues related to NP-hardness that remain poorly understood.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Revisiting deadlock prevention: a probabilistic approach

We revisit the deadlock-prevention problem by focusing on priority digraphs instead of the traditional wait-for digraphs. This has allowed us to formulate deadlock prevention in terms of prohibiting the occurrence of directed cycles even in the most general of wait models (the so-called AND-OR model, in which prohibiting wait-for directed cycles is generally overly restrictive). For a particular case in which the priority digraphs are somewhat simplified, we introduce a Las Vegas probabilistic mechanism for resource granting and analyze its key aspects in detail.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Network algorithmics and the emergence of the cortical synaptic-weight distribution

When a neuron fires and the resulting action potential travels down its axon toward other neurons&#39; dendrites, the effect on each of those neurons is mediated by the weight of the synapse that separates it from the firing neuron. This weight, in turn, is affected by the postsynaptic neuron&#39;s response through a mechanism that is thought to underlie important processes such as learning and memory. Although of difficult quantification, cortical synaptic weights have been found to obey a long-tailed unimodal distribution peaking near the lowest values, thus confirming some of the predictive models built previously. These models are all causally local, in the sense that they refer to the situation in which a number of neurons all fire directly at the same postsynaptic neuron. Consequently, they necessarily embody assumptions regarding the generation of action potentials by the presynaptic neurons that have little biological interpretability. In this letter we introduce a network model of large groups of interconnected neurons and demonstrate, making none of the assumptions that characterize the causally local models, that its long-term behavior gives rise to a distribution of synaptic weights with the same properties that were experimentally observed. In our model the action potentials that create a neuron&#39;s input are, ultimately, the product of network-wide causal chains relating what happens at a neuron to the firings of others. Our model is then of a causally global nature and predicates the emergence of the synaptic-weight distribution on network structure and function. As such, it has the potential to become instrumental also in the study of other emergent cortical phenomena.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions

The field of algorithmic self-assembly is concerned with the design and analysis of self-assembly systems from a computational perspective, that is, from the perspective of mathematical problems whose study may give insight into the natural processes through which elementary objects self-assemble into more complex ones. One of the main problems of algorithmic self-assembly is the minimum tile set problem (MTSP), which asks for a collection of types of elementary objects (called tiles) to be found for the self-assembly of an object having a pre-established shape. Such a collection is to be as concise as possible, thus minimizing supply diversity, while satisfying a set of stringent constraints having to do with the termination and other properties of the self-assembly process from its tile types. We present a study of what we think is the first practical approach to MTSP. Our study starts with the introduction of an evolutionary heuristic to tackle MTSP and includes results from extensive experimentation with the heuristic on the self-assembly of simple objects in two and three dimensions. The heuristic we introduce combines classic elements from the field of evolutionary computation with a problem-specific variant of Pareto dominance into a multi-objective approach to MTSP.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Reachability and recoverability of sink nodes in growing acyclic directed networks

We study the growth of networks from a set of isolated ground nodes by the addition of one new node per time step and also of a fixed number of directed edges leading from the new node to randomly selected nodes already in the network. A fixed-width time window is used so that, in general, only nodes that entered the network within the latest window may receive new incoming edges. The resulting directed network is acyclic at all times and allows some of the ground nodes, then called sinks, to be reached from some of the non-ground nodes. We regard such networks as representative of abstract systems of partially ordered constituents, for example in some of the domains related to technological evolution. Two properties of interest are the number of sinks that can be reached from a randomly chosen non-ground node (its reach) and, for a fixed sink, the number of nonoverlapping directed paths through which the sink can be reached, at a given time, from some of the latest nodes to have entered the network. We demonstrate, by means of simulations and also of analytic characterizations, that reaches are distributed according to a power law and that the desired directed paths are expected to occur in very small numbers, perhaps indicating that recovering sinks late in the process of network growth is strongly sensitive to accidental path disruptions.

0 citations0 reviewsNo code linkedOpen access