On the complexity of rationalizing behavior

We study the complexity of rationalizing choice behavior. We do so by analyzing two polar cases, and a number of intermediate ones. In our most structured case, that is where choice behavior is defined in universal choice domains and satisfies the "weak axiom of revealed preference," finding the complete preorder rationalizing choice behavior is a simple matter. In the polar case, where no restriction whatsoever is imposed, either on choice behavior or on choice domain, finding the complete preordersthat rationalize behavior turns out to be intractable. We show that the task of finding the rationalizing complete preorders is equivalent to a graph problem. This allows the search for existing algorithms in the graph theory literature, for the rationalization of choice.

The evolution of helping and harming on graphs: the return of the inclusive fitness effect.

Evolutionary graph theory has been proposed as providing new fundamental rules for the evolution of co-operation and altruism. But how do these results relate to those of inclusive fitness theory? Here, we carry out a retrospective analysis of the models for the evolution of helping on graphs of Ohtsuki et al. [Nature (2006) 441, 502] and Ohtsuki & Nowak [Proc. R. Soc. Lond. Ser. B Biol. Sci (2006) 273, 2249]. We show that it is possible to translate evolutionary graph theory models into classical kin selection models without disturbing at all the mathematics describing the net effect of selection on helping. Model analysis further demonstrates that costly helping evolves on graphs through limited dispersal and overlapping generations. These two factors are well known to promote relatedness between interacting individuals in spatially structured populations. By allowing more than one individual to live at each node of the graph and by allowing interactions to vary with the distance between nodes, our inclusive fitness model allows us to consider a wider range of biological scenarios leading to the evolution of both helping and harming behaviours on graphs.

Synchronizability of EEG-Based Functional Networks in Early Alzheimer's Disease.

Recently graph theory and complex networks have been widely used as a mean to model functionality of the brain. Among different neuroimaging techniques available for constructing the brain functional networks, electroencephalography (EEG) with its high temporal resolution is a useful instrument of the analysis of functional interdependencies between different brain regions. Alzheimer's disease (AD) is a neurodegenerative disease, which leads to substantial cognitive decline, and eventually, dementia in aged people. To achieve a deeper insight into the behavior of functional cerebral networks in AD, here we study their synchronizability in 17 newly diagnosed AD patients compared to 17 healthy control subjects at no-task, eyes-closed condition. The cross-correlation of artifact-free EEGs was used to construct brain functional networks. The extracted networks were then tested for their synchronization properties by calculating the eigenratio of the Laplacian matrix of the connection graph, i.e., the largest eigenvalue divided by the second smallest one. In AD patients, we found an increase in the eigenratio, i.e., a decrease in the synchronizability of brain networks across delta, alpha, beta, and gamma EEG frequencies within the wide range of network costs. The finding indicates the destruction of functional brain networks in early AD.

Extreme prematurity and intra uterine growth restriction effects in brain network topology at school age

Higher risk for long-term behavioral and emotional sequelae, with attentional problems (with or without hyperactivity) is now becoming one of the hallmarks of extreme premature (EP) birth and birth after pregancy conditions leading to poor intra uterine growth restriction (IUGR) [1,2]. However, little is know so far about the neurostructural basis of these complexe brain functional abnormalities that seem to have their origins in early critical periods of brain development. The development of cortical axonal pathways happens in a series of sequential events. The preterm phase (24-36 post conecptional weeks PCW) is known for being crucial for growth of the thalamocortical fiber bundles as well as for the development of long projectional, commisural and projectional fibers [3]. Is it logical to expect, thus, that being exposed to altered intrauterine environment (altered nutrition) or to extrauterine environment earlier that expected, lead to alterations in the structural organization and, consequently, alter the underlying white matter (WM) structure. Understanding rate and variability of normal brain development, and detect differences from typical development may offer insight into the neurodevelopmental anomalies that can be imaged at later stages. Due to its unique ability to non-invasively visualize and quantify in vivo white matter tracts in the brain, in this study we used diffusion MRI (dMRI) tractography to derive brain graphs [4,5,6]. This relatively simple way of modeling the brain enable us to use graph theory to study topological properties of brain graphs in order to study the effects of EP and IUGR on childrens brain connectivity at age 6 years old.

Implementing statistical learning methods through Bayesian networks. Part 1: a guide to Bayesian parameter estimation using forensic science data

As a thorough aggregation of probability and graph theory, Bayesian networks currently enjoy widespread interest as a means for studying factors that affect the coherent evaluation of scientific evidence in forensic science. Paper I of this series of papers intends to contribute to the discussion of Bayesian networks as a framework that is helpful for both illustrating and implementing statistical procedures that are commonly employed for the study of uncertainties (e.g. the estimation of unknown quantities). While the respective statistical procedures are widely described in literature, the primary aim of this paper is to offer an essentially non-technical introduction on how interested readers may use these analytical approaches - with the help of Bayesian networks - for processing their own forensic science data. Attention is mainly drawn to the structure and underlying rationale of a series of basic and context-independent network fragments that users may incorporate as building blocs while constructing larger inference models. As an example of how this may be done, the proposed concepts will be used in a second paper (Part II) for specifying graphical probability networks whose purpose is to assist forensic scientists in the evaluation of scientific evidence encountered in the context of forensic document examination (i.e. results of the analysis of black toners present on printed or copied documents).

EEG-based functional networks in schizophrenia.

Schizophrenia is often considered as a dysconnection syndrome in which, abnormal interactions between large-scale functional brain networks result in cognitive and perceptual deficits. In this article we apply the graph theoretic measures to brain functional networks based on the resting EEGs of fourteen schizophrenic patients in comparison with those of fourteen matched control subjects. The networks were extracted from common-average-referenced EEG time-series through partial and unpartial cross-correlation methods. Unpartial correlation detects functional connectivity based on direct and/or indirect links, while partial correlation allows one to ignore indirect links. We quantified the network properties with the graph metrics, including mall-worldness, vulnerability, modularity, assortativity, and synchronizability. The schizophrenic patients showed method-specific and frequency-specific changes especially pronounced for modularity, assortativity, and synchronizability measures. However, the differences between schizophrenia patients and normal controls in terms of graph theory metrics were stronger for the unpartial correlation method.

Diffusion dynamics on multiplex networks

We study the time scales associated with diffusion processes that take place on multiplex networks, i.e., on a set of networks linked through interconnected layers. To this end, we propose the construction of a supra-Laplacian matrix, which consists of a dimensional lifting of the Laplacian matrix of each layer of the multiplex network. We use perturbative analysis to reveal analytically the structure of eigenvectors and eigenvalues of the complete network in terms of the spectral properties of the individual layers. The spectrum of the supra-Laplacian allows us to understand the physics of diffusionlike processes on top of multiplex networks.

A note on the degree sequences of graphs with restrictions

Degree sequences of some types of graphs will be studied and characterizedin this paper.

Using Pareto optimality to explore the topology and dynamics of the human connectome.

Graph theory has provided a key mathematical framework to analyse the architecture of human brain networks. This architecture embodies an inherently complex relationship between connection topology, the spatial arrangement of network elements, and the resulting network cost and functional performance. An exploration of these interacting factors and driving forces may reveal salient network features that are critically important for shaping and constraining the brain's topological organization and its evolvability. Several studies have pointed to an economic balance between network cost and network efficiency with networks organized in an 'economical' small-world favouring high communication efficiency at a low wiring cost. In this study, we define and explore a network morphospace in order to characterize different aspects of communication efficiency in human brain networks. Using a multi-objective evolutionary approach that approximates a Pareto-optimal set within the morphospace, we investigate the capacity of anatomical brain networks to evolve towards topologies that exhibit optimal information processing features while preserving network cost. This approach allows us to investigate network topologies that emerge under specific selection pressures, thus providing some insight into the selectional forces that may have shaped the network architecture of existing human brains.

Modelització i simulació de processos dinàmics en xarxes complexes adaptatives

El 1736, Leonhard Euler va ser pioner en l'estudi de la teoria de grafs, i des de llavorsmúltiples autors com Kirchoff, Seymour, etc. continuaren amb l'estudi de la teoria i topologiade grafs. La teoria de xarxes, part de la teoria de grafs, també ha estat estudiada abastament.D'altra banda, la dinàmica de xarxes fou popularitzada per Dan Gillespie el 1977, en el qual proposà un algorisme que permet la simulació discreta i estocàstica d'un sistema de partícules, el qual és la base del treball ja que serveix per dur a terme les simulacions de processos sobre les xarxes complexes. El camp de l'anàlisi de la dinàmica de xarxes, de fet, és un campemergent en l'actualitat; comprèn tant l'anàlisi estadística com la utilització de simulacions persolucionar problemes de la mateixa dinàmica.Les xarxes complexes (xarxes de característiques complexes, sovint xarxes reals) també sónobjecte d'estudi de l'actualitat, sobretot a causa de l'aparició de les xarxes socials. S'han convertiten un paradigma per l'estudi de processos dinàmics en sistemes formats per molts componentsque interactuen entre si de manera molt homogèniaL'objectiu del treball és triple:1. Estudiar i entendre els conceptes bàsics i la topologia de les xarxes complexes, així comdiferents tipus de dinàmiques de processos sobre elles.2. Programar un simulador estocàstic en llenguatge C++ capaç de generar trajectòries mitjantçant l'algorisme de Gillespie tant pel model epidèmic com pel model de dinàmicad'enllaços amb reconnexió.3. Utilitzar el simulador tant per estudiar casos que ja han estat tractats en la literatura comcasos nous que no han estat tractats i que poden ser assimilables a xarxes reals com, perexemple, xarxes socials

Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.

Intrahemispheric cortico-cortical connections of the human auditory cortex.

The human auditory cortex comprises the supratemporal plane and large parts of the temporal and parietal convexities. We have investigated the relevant intrahemispheric cortico-cortical connections using in vivo DSI tractography combined with landmark-based registration, automatic cortical parcellation and whole-brain structural connection matrices in 20 right-handed male subjects. On the supratemporal plane, the pattern of connectivity was related to the architectonically defined early-stage auditory areas. It revealed a three-tier architecture characterized by a cascade of connections from the primary auditory cortex to six adjacent non-primary areas and from there to the superior temporal gyrus. Graph theory-driven analysis confirmed the cascade-like connectivity pattern and demonstrated a strong degree of segregation and hierarchy within early-stage auditory areas. Putative higher-order areas on the temporal and parietal convexities had more widely spread local connectivity and long-range connections with the prefrontal cortex; analysis of optimal community structure revealed five distinct modules in each hemisphere. The pattern of temporo-parieto-frontal connectivity was partially asymmetrical. In conclusion, the human early-stage auditory cortical connectivity, as revealed by in vivo DSI tractography, has strong similarities with that of non-human primates. The modular architecture and hemispheric asymmetry in higher-order regions is compatible with segregated processing streams and lateralization of cognitive functions.

Spectral properties of the Laplacian of multiplex networks.

One of the more challenging tasks in the understanding of dynamical properties of models on top of complex networks is to capture the precise role of multiplex topologies. In a recent paper, Gómez et al. [ Phys. Rev. Lett. 110 028701 (2013)], some of the authors proposed a framework for the study of diffusion processes in such networks. Here, we extend the previous framework to deal with general configurations in several layers of networks and analyze the behavior of the spectrum of the Laplacian of the full multiplex. We derive an interesting decoupling of the problem that allow us to unravel the role played by the interconnections of the multiplex in the dynamical processes on top of them. Capitalizing on this decoupling we perform an asymptotic analysis that allow us to derive analytical expressions for the full spectrum of eigenvalues. This spectrum is used to gain insight into physical phenomena on top of multiplex, specifically, diffusion processes and synchronizability.

A structural bridge between alternant and non-alternant hydrocarbons

A simple set of trimethylene-substituted even, fully-pi-bonded, non-alternant monocycles is shown to have several key features in common with acyclic, even alternant polyenes at the Hückel level. These non-alternant molecules provide a bridge between alternant and non-alternant hydrocarbons. This topic might serve as a useful addition to Hückel theory courses targeted at senior undergraduate students.