Analytical properties of horizontal visibility graphs in the Feigenbaum scenario

Time series are proficiently converted into graphs via the horizontal visibility (HV) algorithm, which prompts interest in its capability for capturing the nature of different classes of series in a network context. We have recently shown [B. Luque et al., PLoS ONE 6, 9 (2011)] that dynamical systems can be studied from a novel perspective via the use of this method. Specifically, the period-doubling and band-splitting attractor cascades that characterize unimodal maps transform into families of graphs that turn out to be independent of map nonlinearity or other particulars. Here, we provide an in depth description of the HV treatment of the Feigenbaum scenario, together with analytical derivations that relate to the degree distributions, mean distances, clustering coefficients, etc., associated to the bifurcation cascades and their accumulation points. We describe how the resultant families of graphs can be framed into a renormalization group scheme in which fixed-point graphs reveal their scaling properties. These fixed points are then re-derived from an entropy optimization process defined for the graph sets, confirming a suggested connection between renormalization group and entropy optimization. Finally, we provide analytical and numerical results for the graph entropy and show that it emulates the Lyapunov exponent of the map independently of its sign.

Horizontal visibility graphs generated by type-I intermittency

The type-I intermittency route to (or out of) chaos is investigated within the horizontal visibility (HV) graph theory. For that purpose, we address the trajectories generated by unimodal maps close to an inverse tangent bifurcation and construct their associatedHVgraphs.We showhowthe alternation of laminar episodes and chaotic bursts imprints a fingerprint in the resulting graph structure. Accordingly, we derive a phenomenological theory that predicts quantitative values for several network parameters. In particular, we predict that the characteristic power-law scaling of the mean length of laminar trend sizes is fully inherited by the variance of the graph degree distribution, in good agreement with the numerics. We also report numerical evidence on how the characteristic power-law scaling of the Lyapunov exponent as a function of the distance to the tangent bifurcation is inherited in the graph by an analogous scaling of block entropy functionals defined on the graph. Furthermore, we are able to recast the full set of HV graphs generated by intermittent dynamics into a renormalization-group framework, where the fixed points of its graph-theoretical renormalization-group flow account for the different types of dynamics.We also establish that the nontrivial fixed point of this flow coincides with the tangency condition and that the corresponding invariant graph exhibits extremal entropic properties.

Quasiperiodic Graphs: Structural Design, Scaling and Entropic Properties

A novel class of graphs, here named quasiperiodic, are const ructed via application of the Horizontal Visibility algorithm to the time series generated along the quasiperiodic route to chaos. We show how the hierarchy of mode-locked regions represented by the Far ey tree is inherited by their associated graphs. We are able to establish, via Renormalization Group (RG) theory, the architecture of the quasiperiodic graphs produced by irrational winding numbers with pure periodic continued fraction. And finally, we demonstrate that the RG fixed-point degree distributions are recovered via optimization of a suitably defined graph entropy

An Inequality for Generalized Chromatic Graphs

Асен Божилов, Недялко Ненов - Нека G е n-върхов граф и редицата от степените на върховете му е d1, d2, . . . , dn, а V(G) е множеството от върховете на G. Степента на върха v бележим с d(v). Най-малкото естествено число r, за което V(G) има r-разлагане V(G) = V1 ∪ V2 ∪ · · · ∪ Vr, Vi ∩ Vj = ∅, , i 6 = j такова, че d(v) ≤ n − |Vi|, ∀v ∈ Vi, i = 1, 2, . . . , r е означено с ϕ(G). В тази работа доказваме неравенството ...

On the k-anonymization of time-varying and multi-layer social graphs

The popularity of online social media platforms provides an unprecedented opportunity to study real-world complex networks of interactions. However, releasing this data to researchers and the public comes at the cost of potentially exposing private and sensitive user information. It has been shown that a naive anonymization of a network by removing the identity of the nodes is not sufficient to preserve users’ privacy. In order to deal with malicious attacks, k -anonymity solutions have been proposed to partially obfuscate topological information that can be used to infer nodes’ identity. In this paper, we study the problem of ensuring k anonymity in time-varying graphs, i.e., graphs with a structure that changes over time, and multi-layer graphs, i.e., graphs with multiple types of links. More specifically, we examine the case in which the attacker has access to the degree of the nodes. The goal is to generate a new graph where, given the degree of a node in each (temporal) layer of the graph, such a node remains indistinguishable from other k-1 nodes in the graph. In order to achieve this, we find the optimal partitioning of the graph nodes such that the cost of anonymizing the degree information within each group is minimum. We show that this reduces to a special case of a Generalized Assignment Problem, and we propose a simple yet effective algorithm to solve it. Finally, we introduce an iterated linear programming approach to enforce the realizability of the anonymized degree sequences. The efficacy of the method is assessed through an extensive set of experiments on synthetic and real-world graphs.

A continuous-time quantum walk kernel for unattributed graphs

Kernel methods provide a way to apply a wide range of learning techniques to complex and structured data by shifting the representational problem from one of finding an embedding of the data to that of defining a positive semidefinite kernel. In this paper, we propose a novel kernel on unattributed graphs where the structure is characterized through the evolution of a continuous-time quantum walk. More precisely, given a pair of graphs, we create a derived structure whose degree of symmetry is maximum when the original graphs are isomorphic. With this new graph to hand, we compute the density operators of the quantum systems representing the evolutions of two suitably defined quantum walks. Finally, we define the kernel between the two original graphs as the quantum Jensen-Shannon divergence between these two density operators. The experimental evaluation shows the effectiveness of the proposed approach. © 2013 Springer-Verlag.

Dirac type condition and Hamiltonian graphs

2010 Mathematics Subject Classification: 05C38, 05C45.

On strongly regular graphs with m2 = qm3 and m3 = qm2

2010 Mathematics Subject Classification: 05C50.

Extremal graphs for the sum of the two largest signless Laplacian eigenvalues

Let G be a simple graph on n vertices and e(G) edges. Consider the signless Laplacian, Q(G) = D + A, where A is the adjacency matrix and D is the diagonal matrix of the vertices degree of G. Let q1(G) and q2(G) be the first and the second largest eigenvalues of Q(G), respectively, and denote by S+ n the star graph with an additional edge. It is proved that inequality q1(G)+q2(G) e(G)+3 is tighter for the graph S+ n among all firefly graphs and also tighter to S+ n than to the graphs Kk _ Kn−k recently presented by Ashraf, Omidi and Tayfeh-Rezaie. Also, it is conjectured that S+ n minimizes f(G) = e(G) − q1(G) − q2(G) among all graphs G on n vertices.

Random walk with restart over dynamic graphs

Random Walk with Restart (RWR) is an appealing measure of proximity between nodes based on graph structures. Since real graphs are often large and subject to minor changes, it is prohibitively expensive to recompute proximities from scratch. Previous methods use LU decomposition and degree reordering heuristics, entailing O(|V|^3) time and O(|V|^2) memory to compute all (|V|^2) pairs of node proximities in a static graph. In this paper, a dynamic scheme to assess RWR proximities is proposed: (1) For unit update, we characterize the changes to all-pairs proximities as the outer product of two vectors. We notice that the multiplication of an RWR matrix and its transition matrix, unlike traditional matrix multiplications, is commutative. This can greatly reduce the computation of all-pairs proximities from O(|V|^3) to O(|delta|) time for each update without loss of accuracy, where |delta| (<<|V|^2) is the number of affected proximities. (2) To avoid O(|V|^2) memory for all pairs of outputs, we also devise efficient partitioning techniques for our dynamic model, which can compute all pairs of proximities segment-wisely within O(l|V|) memory and O(|V|/l) I/O costs, where 1<=l<=|V| is a user-controlled trade-off between memory and I/O costs. (3) For bulk updates, we also devise aggregation and hashing methods, which can discard many unnecessary updates further and handle chunks of unit updates simultaneously. Our experimental results on various datasets demonstrate that our methods can be 1–2 orders of magnitude faster than other competitors while securing scalability and exactness.

Bio-QA-GNN: Reasoning with Language Models and Knowledge Graphs for Interpretable Biomedical Question Answering

Nowadays the idea of injecting world or domain-specific structured knowledge into pre-trained language models (PLMs) is becoming an increasingly popular approach for solving problems such as biases, hallucinations, huge architectural sizes, and explainability lack—critical for real-world natural language processing applications in sensitive fields like bioinformatics. One recent work that has garnered much attention in Neuro-symbolic AI is QA-GNN, an end-to-end model for multiple-choice open-domain question answering (MCOQA) tasks via interpretable text-graph reasoning. Unlike previous publications, QA-GNN mutually informs PLMs and graph neural networks (GNNs) on top of relevant facts retrieved from knowledge graphs (KGs). However, taking a more holistic view, existing PLM+KG contributions mainly consider commonsense benchmarks and ignore or shallowly analyze performances on biomedical datasets. This thesis start from a propose of a deep investigation of QA-GNN for biomedicine, comparing existing or brand-new PLMs, KGs, edge-aware GNNs, preprocessing techniques, and initialization strategies. By combining the insights emerged in DISI's research, we introduce Bio-QA-GNN that include a KG. Working with this part has led to an improvement in state-of-the-art of MCOQA model on biomedical/clinical text, largely outperforming the original one (+3.63\% accuracy on MedQA). Our findings also contribute to a better understanding of the explanation degree allowed by joint text-graph reasoning architectures and their effectiveness on different medical subjects and reasoning types. Codes, models, datasets, and demos to reproduce the results are freely available at: \url{https://github.com/disi-unibo-nlp/bio-qagnn}.

The Crosslinking Degree Controls The Mechanical, Rheological, And Swelling Properties Of Hyaluronic Acid Microparticles.

Viscosupplements, used for treating joint and cartilage diseases, restore the rheological properties of synovial fluid, regulate joint homeostasis and act as scaffolds for cell growth and tissue regeneration. Most viscosupplements are hydrogels composed of hyaluronic acid (HA) microparticles suspended in fluid HA. These microparticles are crosslinked with chemicals to assure their stability against enzyme degradation and to prolong the action of the viscosupplement. However, the crosslinking also modifies the mechanical, swelling and rheological properties of the HA microparticle hydrogels, with consequences on the effectiveness of the application. The aim of this study is to correlate the crosslinking degree (CD) with these properties to achieve modulation of HA/DVS microparticles through CD control. Because divinyl sulfone (DVS) is the usual crosslinker of HA in viscosupplements, we examined the effects of CD by preparing HA microparticles at 1:1, 2:1, 3:1, and 5:1 HA/DVS mass ratios. The CD was calculated from inductively coupled plasma spectrometry data. HA microparticles were previously sized to a mean diameter of 87.5 µm. Higher CD increased the viscoelasticity and the extrusion force and reduced the swelling of the HA microparticle hydrogels, which also showed Newtonian pseudoplastic behavior and were classified as covalent weak. The hydrogels were not cytotoxic to fibroblasts according to an MTT (3-[4,5-dimethylthiazol-2-yl]-2,5-diphenyltetrazolium bromide) assay. © 2014 Wiley Periodicals, Inc. J Biomed Mater Res Part A, 2014.

Histologic Correlation Of Expression Of Ki-67 In Squamous Cell Carcinoma Of The Glottis According To The Degree Of Cell Differentiation.

Squamous cell carcinoma is the most common neoplasm of the larynx and glottis, and its prognosis depends on the size of the lesion, level of local invasion, cervical lymphatic spread, and presence of distant metastases. Ki-67 (MKI67) is a protein present in the core, whose function is related to cell proliferation. To evaluate the expression of marker Ki-67 in squamous cell carcinoma of the larynx and glottis and its correlation to pathological findings. Experimental study with immunohistochemistry analysis of Ki-67, calculating the percentage of the cell proliferation index in glottic squamous cell carcinomas. Sixteen cases were analyzed, with six well-differentiated and 10 poorly/moderately differentiated tumors. There was a correlation between cell proliferation index and degree of cell differentiation, with higher proliferation in poorly/moderately differentiated tumors. The cell proliferation index, as measured by Ki-67, may be useful in the characterization of histological degree in glottic squamous cell tumors.

Risk Of Leukemia In First Degree Relatives Of Patients With Nonsyndromic Cleft Lip And Palate.

The aim of this study was to determine the frequency of leukemia in parents of patients with nonsyndromic cleft lip and/or cleft palate (NSCL/P). This case-control study evaluated first-degree family members of 358 patients with NSCL/P and 1,432 subjects without craniofacial alterations or syndromes. Statistical analysis was carried out using Fisher's test. From the 358 subjects with NSCL/P, 3 first-degree parents had history of leukemia, while 2 out of 1,432 subjects from the unaffected group had a family history of leukemia. The frequency of positive family history of leukemia was not significantly increased in first-degree relatives of patients with NSCL/P.

Effect Of 4-(n,n-dimethylamino)phenethyl Alcohol On Degree Of Conversion And Cytotoxicity Of Photo-polymerized Cq-based Resin Composites.

The aim of this study was to evaluate the degree of conversion (DC) and the cytotoxicity of photo-cured experimental resin composites containing 4-(N,N-dimethylamino)phenethyl alcohol (DMPOH) combined to the camphorquinone (CQ) compared with ethylamine benzoate (EDAB). The resin composites were mechanically blended using 35 wt% of an organic matrix and 65 wt% of filler loading. To this matrix was added 0.2 wt% of CQ and 0.2 wt% of one of the reducing agents tested. 5x1 mm samples (n=5) were previously submitted to DC measurement and then pre-immersed in complete culture medium without 10% (v/v) bovine serum for 1 h or 24 h at 37 °C in a humidifier incubator with 5% CO2 and 95% humidity to evaluate the cytotoxic effects of experimental resin composites using the MTT assay on immortalized human keratinocytes cells. As a result of absence of normal distribution, the statistical analysis was performed using the nonparametric Kruskal-Wallis to evaluate the cytotoxicity and one-way analysis of variance to evaluate the DC. For multiple comparisons, cytotoxicity statistical analyses were submitted to Student-Newman-Keuls and DC analysis to Tukey's HSD post-hoc test (=0.05). No significant differences were found between the DC of DMPOH (49.9%) and EDAB (50.7%). 1 h outcomes showed no significant difference of the cell viability between EDAB (99.26%), DMPOH (94.85%) and the control group (100%). After 24 h no significant difference were found between EDAB (48.44%) and DMPOH (38.06%), but significant difference was found compared with the control group (p>0.05). DMPOH presented similar DC and cytotoxicity compared with EDAB when associated with CQ.