ResearchPad - graph-theory https://www.researchpad.co Default RSS Feed en-us © 2020 Newgen KnowledgeWorks <![CDATA[Familial assimilation in transmission of raw-freshwater fish-eating practice leading to clonorchiasis]]> https://www.researchpad.co/article/elastic_article_15763 Clonorchiasis is caused by the ingestion of raw freshwater fish, which contains the infective larvae of Clonorchis sinensis. It is highly endemic in Asia, where about 15 million people are afflicted. To establish sustainable control strategy, the transmission of raw-eating practice needs to be illuminated. In this study, we conducted a survey in school students from four clonorchiasis endemic provinces in China, covering 23,222 students aged 9–18. The characteristics of raw-eating practice, impact of parents’ raw-eating practice on children, interaction of spouses’ practice was explored. It is demonstrated that raw-eating practice presents familial clustering, which is higher in those families with older children and with boys. Raw-eating practice in children is highly influenced by their parents’ raw-eating practice especially when both parents do. Additionally, there exists interaction between spouses’ raw-eating practice. The impact of husband’s raw-eating practice on his wife is higher than that of wife’s raw-eating practice on her husband. Familial assimilation dominates the transmission of raw-freshwater eating-practice, including the assimilation from parents to their children and that between spouses. This finding indicates the adoption of sustainable strategy against clonorchiasis through blocking raw-freshwater fish-eating practice.

]]>
<![CDATA[Consensus based SoC trajectory tracking control design for economic-dispatched distributed battery energy storage system]]> https://www.researchpad.co/article/elastic_article_14556 The state-of-charge (SoC) of an energy storage system (ESS) should be kept in a certain safe range for ensuring its state-of-health (SoH) as well as higher efficiency. This procedure maximizes the power capacity of the ESSs all the times. Furthermore, economic load dispatch (ELD) is implemented to allocate power among various ESSs, with the aim of fully meeting the load demand and reducing the total operating cost. In this research article, a distributed multi-agent consensus based control algorithm is proposed for multiple battery energy storage systems (BESSs), operating in a microgrid (MG), for fulfilling several objectives, including: SoC trajectories tracking control, economic load dispatch, active and reactive power sharing control, and voltage and frequency regulation (using the leader-follower consensus approach). The proposed algorithm considers the hierarchical control structure of the BESSs and the frequency/voltage droop controllers with limited information exchange among the BESSs. It embodies both self and communication time-delays, and achieves its objectives along with offering plug-and-play capability and robustness against communication link failure. Matlab/Simulink platform is used to test and validate the performance of the proposed algorithm under load disturbances through extensive simulations carried out on a modified IEEE 57-bus system. A detailed comparative analysis of the proposed distributed control strategy is carried out with the distributed PI-based conventional control strategy for demonstrating its superior performance.

]]>
<![CDATA[‘In search of lost time’: Identifying the causative role of cumulative competition load and competition time-loss in professional tennis using a structural nested mean model]]> https://www.researchpad.co/article/N4f3da08e-598e-44d5-a4f3-a2c64fcebd1f

Injury prevention is critical to the achievement of peak performance in elite sport. For professional tennis players, the topic of injury prevention has gained even greater importance in recent years as multiple of the best male players have been sidelined owing to injury. Identifying potential causative factors of injury is essential for the development of effective prevention strategies, yet such research is hampered by incomplete data, the complexity of injury etiology, and observational study biases. The present study attempts to address these challenges by focusing on competition load and time-loss to competition—a completely observable risk factor and outcome—and using a structural nested mean model (SNMM) to identify the potential causal role of cumulative competition load on the risk of time-loss. Using inverse probability of treatment weights to balance exposure histories with respect to player ability, past injury, and consecutive competition weeks at each time point; the SNMM analysis of 389 professional male players and 55,773 weeks of competition found that total load significantly increases the risk of time-loss (HR = 1.05 per 1,000 games of additional load 95% CI 1.01-1.10) and this effect becomes magnified with age. Standard regression showed a protective effect of load, highlighting the value of more robust causal methods in the study of dynamic exposures and injury in sport and the need for further applications of these methods for understanding how time-loss and injuries of elite athletes might be prevented in the future.

]]>
<![CDATA[Exponential random graph model parameter estimation for very large directed networks]]> https://www.researchpad.co/article/N437fb42a-ebf8-44aa-9399-d12b1354408e

Exponential random graph models (ERGMs) are widely used for modeling social networks observed at one point in time. However the computational difficulty of ERGM parameter estimation has limited the practical application of this class of models to relatively small networks, up to a few thousand nodes at most, with usually only a few hundred nodes or fewer. In the case of undirected networks, snowball sampling can be used to find ERGM parameter estimates of larger networks via network samples, and recently published improvements in ERGM network distribution sampling and ERGM estimation algorithms have allowed ERGM parameter estimates of undirected networks with over one hundred thousand nodes to be made. However the implementations of these algorithms to date have been limited in their scalability, and also restricted to undirected networks. Here we describe an implementation of the recently published Equilibrium Expectation (EE) algorithm for ERGM parameter estimation of large directed networks. We test it on some simulated networks, and demonstrate its application to an online social network with over 1.6 million nodes.

]]>
<![CDATA[Normalization enhances brain network features that predict individual intelligence in children with epilepsy]]> https://www.researchpad.co/article/5c8823aad5eed0c484638dcf

Background and purpose

Architecture of the cerebral network has been shown to associate with IQ in children with epilepsy. However, subject-level prediction on this basis, a crucial step toward harnessing network analyses for the benefit of children with epilepsy, has yet to be achieved. We compared two network normalization strategies in terms of their ability to optimize subject-level inferences on the relationship between brain network architecture and brain function.

Materials and methods

Patients with epilepsy and resting state fMRI were retrospectively identified. Brain network nodes were defined by anatomic parcellation, first in patient space (nodes defined for each patient) and again in template space (same nodes for all patients). Whole-brain weighted graphs were constructed according to pair-wise correlation of BOLD-signal time courses between nodes. The following metrics were then calculated: clustering coefficient, transitivity, modularity, path length, and global efficiency. Metrics computed on graphs in patient space were normalized to the same metric computed on a random network of identical size. A machine learning algorithm was used to predict patient IQ given access to only the network metrics.

Results

Twenty-seven patients (8–18 years) comprised the final study group. All brain networks demonstrated expected small world properties. Accounting for intrinsic population heterogeneity had a significant effect on prediction accuracy. Specifically, transformation of all patients into a common standard space as well as normalization of metrics to those computed on a random network both substantially outperformed the use of non-normalized metrics.

Conclusion

Normalization contributed significantly to accurate subject-level prediction of cognitive function in children with epilepsy. These findings support the potential for quantitative network approaches to contribute clinically meaningful information in children with neurological disorders.

]]>
<![CDATA[Description of network meta-analysis geometry: A metrics design study]]> https://www.researchpad.co/article/5c76fe29d5eed0c484e5b60f

Background

The conduction and report of network meta-analysis (NMA), including the presentation of the network-plot, should be transparent. We aimed to propose metrics adapted from graph theory and social network-analysis literature to numerically describe NMA geometry.

Methods

A previous systematic review of NMAs of pharmacological interventions was performed. Data on the graph’s presentation were collected. Network-plots were reproduced using Gephi 0.9.1. Eleven geometric metrics were tested. The Spearman test for non-parametric correlation analyses and the Bland-Altman and Lin’s Concordance tests were performed (IBM SPSS Statistics 24.0).

Results

From the 477 identified NMAs only 167 graphs could be reproduced because they provided enough information on the plot characteristics. The median nodes and edges were 8 (IQR 6–11) and 10 (IQR 6–16), respectively, with 22 included studies (IQR 13–35). Metrics such as density (median 0.39, ranged 0.07–1.00), median thickness (2.0, IQR 1.0–3.0), percentages of common comparators (median 68%), and strong edges (median 53%) were found to contribute to the description of NMA geometry. Mean thickness, average weighted degree and average path length produced similar results than other metrics, but they can lead to misleading conclusions.

Conclusions

We suggest the incorporation of seven simple metrics to report NMA geometry. Editors and peer-reviews should ensure that guidelines for NMA report are strictly followed before publication.

]]>
<![CDATA[Hierarchical patient-centric caregiver network method for clinical outcomes study]]> https://www.researchpad.co/article/5c6dca0dd5eed0c48452a709

In clinical outcome studies, analysis has traditionally been performed using patient-level factors, with minor attention given to provider-level features. However, the nature of care coordination and collaboration between caregivers (providers) may also be important in determining patient outcomes. Using data from patients admitted to intensive care units at a large tertiary care hospital, we modeled the caregivers that provided medical service to a specific patient as patient-centric subnetwork embedded within larger caregiver networks of the institute. The caregiver networks were composed of caregivers who treated either a cohort of patients with particular disease or any patient regardless of disease. Our model can generate patient-specific caregiver network features at multiple levels, and we demonstrate that these multilevel network features, in addition to patient-level features, are significant predictors of length of hospital stay and in-hospital mortality.

]]>
<![CDATA[Network-based features enable prediction of essential genes across diverse organisms]]> https://www.researchpad.co/article/5c1c0b06d5eed0c484427271

Machine learning approaches to predict essential genes have gained a lot of traction in recent years. These approaches predominantly make use of sequence and network-based features to predict essential genes. However, the scope of network-based features used by the existing approaches is very narrow. Further, many of these studies focus on predicting essential genes within the same organism, which cannot be readily used to predict essential genes across organisms. Therefore, there is clearly a need for a method that is able to predict essential genes across organisms, by leveraging network-based features. In this study, we extract several sets of network-based features from protein–protein association networks available from the STRING database. Our network features include some common measures of centrality, and also some novel recursive measures recently proposed in social network literature. We extract hundreds of network-based features from networks of 27 diverse organisms to predict the essentiality of 87000+ genes. Our results show that network-based features are statistically significantly better at classifying essential genes across diverse bacterial species, compared to the current state-of-the-art methods, which use mostly sequence and a few ‘conventional’ network-based features. Our diverse set of network properties gave an AUROC of 0.847 and a precision of 0.320 across 27 organisms. When we augmented the complete set of network features with sequence-derived features, we achieved an improved AUROC of 0.857 and a precision of 0.335. We also constructed a reduced set of 100 sequence and network features, which gave a comparable performance. Further, we show that our features are useful for predicting essential genes in new organisms by using leave-one-species-out validation. Our network features capture the local, global and neighbourhood properties of the network and are hence effective for prediction of essential genes across diverse organisms, even in the absence of other complex biological knowledge. Our approach can be readily exploited to predict essentiality for organisms in interactome databases such as the STRING, where both network and sequence are readily available. All codes are available at https://github.com/RamanLab/nbfpeg.

]]>
<![CDATA[Hierarchical elimination selection method of dendritic river network generalization]]> https://www.researchpad.co/article/5c0ed773d5eed0c484f1417c

Dendritic river networks are fundamental elements in cartography, and the generalization of these river networks directly influences the quality of cartographic generalization. Automatic selection is a difficult and important process for river generalization that requires the consideration of semantic, geometric, topological, and structural characteristics. However, owing to a lack of effective use of river features, most existing methods lose important spatial distribution characteristics of rivers, thus affecting the selection result. Therefore, a hierarchical elimination selection method of dendritic river networks is proposed that consists of three steps. First, a directed topology tree (DTT) is investigated to realize the organization of river data and the intelligent identification of river structures. Second, based on the “180° hypothesis” and “acute angle hypothesis”, each river is traced in the upstream direction from its estuary to create the stroke connections of dendritic river networks based on a consideration of the river semantics, length, and angle features, and the hierarchical relationships of a dendritic river network are then determined. Finally, by determining the total number of selected rivers, a hierarchical elimination algorithm that accounts for density differences is proposed. The reliability of the proposed method was verified using sample data tests, and the rationality and validity of the method were demonstrated in experiments using actual data.

]]>
<![CDATA[Measurement and simulation of the relatively competitive advantages and weaknesses between economies based on bipartite graph theory]]> https://www.researchpad.co/article/5b28b13a463d7e116be9c9a7

The input-output table is very comprehensive and detailed in describing the national economic systems with abundant economic relationships, which contain supply and demand information among various industrial sectors. The complex network, a theory, and method for measuring the structure of a complex system can depict the structural characteristics of the internal structure of the researched object by measuring the structural indicators of the social and economic systems, revealing the complex relationships between the inner hierarchies and the external economic functions. In this paper, functions of industrial sectors on the global value chain are to be distinguished with bipartite graph theory, and inter-sector competitive relationships are to be extracted through resource allocation process. Furthermore, quantitative analysis indices will be proposed under the perspective of a complex network, which will be used to bring about simulations on the variation tendencies of economies’ status in different situations of commercial intercourses. Finally, a new econophysics analytical framework of international trade is to be established.

]]>
<![CDATA[Analysis of Graph Invariants in Functional Neocortical Circuitry Reveals Generalized Features Common to Three Areas of Sensory Cortex]]> https://www.researchpad.co/article/5989dae0ab0ee8fa60bbb8f4

Correlations in local neocortical spiking activity can provide insight into the underlying organization of cortical microcircuitry. However, identifying structure in patterned multi-neuronal spiking remains a daunting task due to the high dimensionality of the activity. Using two-photon imaging, we monitored spontaneous circuit dynamics in large, densely sampled neuronal populations within slices of mouse primary auditory, somatosensory, and visual cortex. Using the lagged correlation of spiking activity between neurons, we generated functional wiring diagrams to gain insight into the underlying neocortical circuitry. By establishing the presence of graph invariants, which are label-independent characteristics common to all circuit topologies, our study revealed organizational features that generalized across functionally distinct cortical regions. Regardless of sensory area, random and -nearest neighbors null graphs failed to capture the structure of experimentally derived functional circuitry. These null models indicated that despite a bias in the data towards spatially proximal functional connections, functional circuit structure is best described by non-random and occasionally distal connections. Eigenvector centrality, which quantifies the importance of a neuron in the temporal flow of circuit activity, was highly related to feedforwardness in all functional circuits. The number of nodes participating in a functional circuit did not scale with the number of neurons imaged regardless of sensory area, indicating that circuit size is not tied to the sampling of neocortex. Local circuit flow comprehensively covered angular space regardless of the spatial scale that we tested, demonstrating that circuitry itself does not bias activity flow toward pia. Finally, analysis revealed that a minimal numerical sample size of neurons was necessary to capture at least 90 percent of functional circuit topology. These data and analyses indicated that functional circuitry exhibited rules of organization which generalized across three areas of sensory neocortex.

]]>
<![CDATA[Reproducibility and Robustness of Graph Measures of the Associative-Semantic Network]]> https://www.researchpad.co/article/5989daa5ab0ee8fa60ba72cf

Graph analysis is a promising tool to quantify brain connectivity. However, an essential requirement is that the graph measures are reproducible and robust. We have studied the reproducibility and robustness of various graph measures in group based and in individual binary and weighted networks derived from a task fMRI experiment during explicit associative-semantic processing of words and pictures. The nodes of the network were defined using an independent study and the connectivity was based on the partial correlation of the time series between any pair of nodes. The results showed that in case of binary networks, global graph measures exhibit a good reproducibility and robustness for networks which are not too sparse and these figures of merit depend on the graph measure and on the density of the network. Furthermore, group based binary networks should be derived from groups of sufficient size and the lower the density the more subjects are required to obtain robust values. Local graph measures are very variable in terms of reproducibility and should be interpreted with care. For weighted networks, we found good reproducibility (average test-retest variability <5% and ICC values >0.4) when using subject specific networks and this will allow us to relate network properties to individual subject information.

]]>
<![CDATA[On the Origins and Control of Community Types in the Human Microbiome]]> https://www.researchpad.co/article/5989db3dab0ee8fa60bd59cf

Microbiome-based stratification of healthy individuals into compositional categories, referred to as “enterotypes” or “community types”, holds promise for drastically improving personalized medicine. Despite this potential, the existence of community types and the degree of their distinctness have been highly debated. Here we adopted a dynamic systems approach and found that heterogeneity in the interspecific interactions or the presence of strongly interacting species is sufficient to explain community types, independent of the topology of the underlying ecological network. By controlling the presence or absence of these strongly interacting species we can steer the microbial ecosystem to any desired community type. This open-loop control strategy still holds even when the community types are not distinct but appear as dense regions within a continuous gradient. This finding can be used to develop viable therapeutic strategies for shifting the microbial composition to a healthy configuration.

]]>
<![CDATA[Comparing the Hierarchy of Keywords in On-Line News Portals]]> https://www.researchpad.co/article/5989da51ab0ee8fa60b8ddef

Hierarchical organization is prevalent in networks representing a wide range of systems in nature and society. An important example is given by the tag hierarchies extracted from large on-line data repositories such as scientific publication archives, file sharing portals, blogs, on-line news portals, etc. The tagging of the stored objects with informative keywords in such repositories has become very common, and in most cases the tags on a given item are free words chosen by the authors independently. Therefore, the relations among keywords appearing in an on-line data repository are unknown in general. However, in most cases the topics and concepts described by these keywords are forming a latent hierarchy, with the more general topics and categories at the top, and more specialized ones at the bottom. There are several algorithms available for deducing this hierarchy from the statistical features of the keywords. In the present work we apply a recent, co-occurrence-based tag hierarchy extraction method to sets of keywords obtained from four different on-line news portals. The resulting hierarchies show substantial differences not just in the topics rendered as important (being at the top of the hierarchy) or of less interest (categorized low in the hierarchy), but also in the underlying network structure. This reveals discrepancies between the plausible keyword association frameworks in the studied news portals.

]]>
<![CDATA[Multitask Learning of Signaling and Regulatory Networks with Application to Studying Human Response to Flu]]> https://www.researchpad.co/article/5989db0bab0ee8fa60bca384

Reconstructing regulatory and signaling response networks is one of the major goals of systems biology. While several successful methods have been suggested for this task, some integrating large and diverse datasets, these methods have so far been applied to reconstruct a single response network at a time, even when studying and modeling related conditions. To improve network reconstruction we developed MT-SDREM, a multi-task learning method which jointly models networks for several related conditions. In MT-SDREM, parameters are jointly constrained across the networks while still allowing for condition-specific pathways and regulation. We formulate the multi-task learning problem and discuss methods for optimizing the joint target function. We applied MT-SDREM to reconstruct dynamic human response networks for three flu strains: H1N1, H5N1 and H3N2. Our multi-task learning method was able to identify known and novel factors and genes, improving upon prior methods that model each condition independently. The MT-SDREM networks were also better at identifying proteins whose removal affects viral load indicating that joint learning can still lead to accurate, condition-specific, networks. Supporting website with MT-SDREM implementation: http://sb.cs.cmu.edu/mtsdrem

]]>
<![CDATA[GIANT: A Cytoscape Plugin for Modular Networks]]> https://www.researchpad.co/article/5989db02ab0ee8fa60bc6fb3

Network analysis provides deep insight into real complex systems. Revealing the link between topological and functional role of network elements can be crucial to understand the mechanisms underlying the system. Here we propose a Cytoscape plugin (GIANT) to perform network clustering and characterize nodes at the light of a modified Guimerà-Amaral cartography. This approach results into a vivid picture of the a topological/functional relationship at both local and global level. The plugin has been already approved and uploaded on the Cytoscape APP store.

]]>
<![CDATA[Consensus between Pipelines in Structural Brain Networks]]> https://www.researchpad.co/article/5989db1fab0ee8fa60bcef51

Structural brain networks may be reconstructed from diffusion MRI tractography data and have great potential to further our understanding of the topological organisation of brain structure in health and disease. Network reconstruction is complex and involves a series of processesing methods including anatomical parcellation, registration, fiber orientation estimation and whole-brain fiber tractography. Methodological choices at each stage can affect the anatomical accuracy and graph theoretical properties of the reconstructed networks, meaning applying different combinations in a network reconstruction pipeline may produce substantially different networks. Furthermore, the choice of which connections are considered important is unclear. In this study, we assessed the similarity between structural networks obtained using two independent state-of-the-art reconstruction pipelines. We aimed to quantify network similarity and identify the core connections emerging most robustly in both pipelines. Similarity of network connections was compared between pipelines employing different atlases by merging parcels to a common and equivalent node scale. We found a high agreement between the networks across a range of fiber density thresholds. In addition, we identified a robust core of highly connected regions coinciding with a peak in similarity across network density thresholds, and replicated these results with atlases at different node scales. The binary network properties of these core connections were similar between pipelines but showed some differences in atlases across node scales. This study demonstrates the utility of applying multiple structural network reconstrution pipelines to diffusion data in order to identify the most important connections for further study.

]]>
<![CDATA[Identification of Conserved Moieties in Metabolic Networks by Graph Theoretical Analysis of Atom Transition Networks]]> https://www.researchpad.co/article/5989daa5ab0ee8fa60ba71b1

Conserved moieties are groups of atoms that remain intact in all reactions of a metabolic network. Identification of conserved moieties gives insight into the structure and function of metabolic networks and facilitates metabolic modelling. All moiety conservation relations can be represented as nonnegative integer vectors in the left null space of the stoichiometric matrix corresponding to a biochemical network. Algorithms exist to compute such vectors based only on reaction stoichiometry but their computational complexity has limited their application to relatively small metabolic networks. Moreover, the vectors returned by existing algorithms do not, in general, represent conservation of a specific moiety with a defined atomic structure. Here, we show that identification of conserved moieties requires data on reaction atom mappings in addition to stoichiometry. We present a novel method to identify conserved moieties in metabolic networks by graph theoretical analysis of their underlying atom transition networks. Our method returns the exact group of atoms belonging to each conserved moiety as well as the corresponding vector in the left null space of the stoichiometric matrix. It can be implemented as a pipeline of polynomial time algorithms. Our implementation completes in under five minutes on a metabolic network with more than 4,000 mass balanced reactions. The scalability of the method enables extension of existing applications for moiety conservation relations to genome-scale metabolic networks. We also give examples of new applications made possible by elucidating the atomic structure of conserved moieties.

]]>
<![CDATA[TripNet: A Method for Constructing Rooted Phylogenetic Networks from Rooted Triplets]]> https://www.researchpad.co/article/5989da15ab0ee8fa60b7af6e

The problem of constructing an optimal rooted phylogenetic network from an arbitrary set of rooted triplets is an NP-hard problem. In this paper, we present a heuristic algorithm called TripNet, which tries to construct a rooted phylogenetic network with the minimum number of reticulation nodes from an arbitrary set of rooted triplets. Despite of current methods that work for dense set of rooted triplets, a key innovation is the applicability of TripNet to non-dense set of rooted triplets. We prove some theorems to clarify the performance of the algorithm. To demonstrate the efficiency of TripNet, we compared TripNet with SIMPLISTIC. It is the only available software which has the ability to return some rooted phylogenetic network consistent with a given dense set of rooted triplets. But the results show that for complex networks with high levels, the SIMPLISTIC running time increased abruptly. However in all cases TripNet outputs an appropriate rooted phylogenetic network in an acceptable time. Also we tetsed TripNet on the Yeast data. The results show that Both TripNet and optimal networks have the same clustering and TripNet produced a level-3 network which contains only one more reticulation node than the optimal network.

]]>
<![CDATA[Reduced Theta-Band Power and Phase Synchrony during Explicit Verbal Memory Tasks in Female, Non-Clinical Individuals with Schizotypal Traits]]> https://www.researchpad.co/article/5989daabab0ee8fa60ba93c8

The study of non-clinical individuals with schizotypal traits has been considered to provide a promising endophenotypic approach to understanding schizophrenia, because schizophrenia is highly heterogeneous, and a number of confounding factors may affect neuropsychological performance. Here, we investigated whether deficits in explicit verbal memory in individuals with schizotypal traits are associated with abnormalities in the local and inter-regional synchrony of brain activity. Memory deficits have been recognized as a core problem in schizophrenia, and previous studies have consistently shown explicit verbal memory impairment in schizophrenic patients. However, the mechanism of this impairment has not been fully revealed. Seventeen individuals with schizotypal traits and 17 age-matched, normal controls participated. Multichannel event-related electroencephalograms (EEGs) were recorded while the subjects performed a continuous recognition task. Event-related spectral perturbations (ERSPs) and inter-regional theta-band phase locking values (TPLVs) were investigated to determine the differences in local and global neural synchrony between the two subject groups. Additionally, the connection patterns of the TPLVs were quantitatively analyzed using graph theory measures. An old/new effect was found in the induced theta-band ERSP in both groups. However, the difference between the old and new was larger in normal controls than in schizotypal trait group. The tendency of elevated old/new effect in normal controls was observed in anterior-posterior theta-band phase synchrony as well. Our results suggest that explicit memory deficits observed in schizophrenia patients can also be found in non-clinical individuals with psychometrically defined schizotypal traits.

]]>