Near linear time algorithm to detect community structures in large-scale networks

To Embed or Not: Network Embedding as a Paradigm in Computational Biology

Current technology is producing high throughput biomedical data at an ever-growing rate. A common approach to interpreting such data is through network-based analyses. Since biological networks are notoriously complex and hard to decipher, a growing body of work applies graph embedding techniques to simplify, visualize, and facilitate the analysis of the resulting networks. In this review, we survey traditional and new approaches for graph embedding and compare their application to fundamental problems in network biology with using the networks directly. We consider a broad variety of applications including protein network alignment, community detection, and protein function prediction. We find that in all of these domains both types of approaches are of value and their performance depends on the evaluation measures being used and the goal of the project. In particular, network embedding methods outshine direct methods according to some of those measures and are, thus, an essential tool in bioinformatics research.

Fast consensus clustering in complex networks

Algorithms for community detection are usually stochastic, leading to different partitions for different choices of random seeds. Consensus clustering has proven to be an effective technique to derive more stable and accurate partitions than the ones obtained by the direct application of the algorithm. However, the procedure requires the calculation of the consensus matrix, which can be quite dense if (some of) the clusters of the input partitions are large. Consequently, the complexity can get dangerously close to quadratic, which makes the technique inapplicable on large graphs. Here, we present a fast variant of consensus clustering, which calculates the consensus matrix only on the links of the original graph and on a comparable number of additional node pairs, suitably chosen. This brings the complexity down to linear, while the performance remains comparable as the full technique. Therefore, our fast consensus clustering procedure can be applied on networks with millions of nodes and links.

From Louvain to Leiden: guaranteeing well-connected communities

Community detection is often used to understand the structure of large and complex networks. One of the most popular algorithms for uncovering community structure is the so-called Louvain algorithm. We show that this algorithm has a major defect that largely went unnoticed until now: the Louvain algorithm may yield arbitrarily badly connected communities. In the worst case, communities may even be disconnected, especially when running the algorithm iteratively. In our experimental analysis, we observe that up to 25% of the communities are badly connected and up to 16% are disconnected. To address this problem, we introduce the Leiden algorithm. We prove that the Leiden algorithm yields communities that are guaranteed to be connected. In addition, we prove that, when the Leiden algorithm is applied iteratively, it converges to a partition in which all subsets of all communities are locally optimally assigned. Furthermore, by relying on a fast local move approach, the Leiden algorithm runs faster than the Louvain algorithm. We demonstrate the performance of the Leiden algorithm for several benchmark and real-world networks. We find that the Leiden algorithm is faster than the Louvain algorithm and uncovers better partitions, in addition to providing explicit guarantees.

Graph-Based Community Detection for Decoy Selection in Template-Free Protein Structure Prediction

Significant efforts in wet and dry laboratories are devoted to resolving molecular structures. In particular, computational methods can now compute thousands of tertiary structures that populate the structure space of a protein molecule of interest. These advances are now allowing us to turn our attention to analysis methodologies that are able to organize the computed structures in order to highlight functionally relevant structural states. In this paper, we propose a methodology that leverages community detection methods, designed originally to detect communities in social networks, to organize computationally probed protein structure spaces. We report a principled comparison of such methods along several metrics on proteins of diverse folds and lengths. We present a rigorous evaluation in the context of decoy selection in template-free protein structure prediction. The results make the case that network-based community detection methods warrant further investigation to advance analysis of protein structure spaces for automated selection of functionally relevant structures.

A Comparative Study of Cluster Detection Algorithms in Protein-Protein Interaction for Drug Target Discovery and Drug Repurposing

The interactions between drugs and their target proteins induce altered expression of genes involved in complex intracellular networks. The properties of these functional network modules are critical for the identification of drug targets, for drug repurposing, and for understanding the underlying mode of action of the drug. The topological modules generated by a computational approach are defined as functional clusters. However, the functions inferred for these topological modules extracted from a large-scale molecular interaction network, such as a protein–protein interaction (PPI) network, could differ depending on different cluster detection algorithms. Moreover, the dynamic gene expression profiles among tissues or cell types causes differential functional interaction patterns between the molecular components. Thus, the connections in the PPI network should be modified by the transcriptomic landscape of specific cell lines before producing topological clusters. Here, we systematically investigated the clusters of a cell-based PPI network by using four cluster detection algorithms. We subsequently compared the performance of these algorithms for target gene prediction, which integrates gene perturbation data with the cell-based PPI network using two drug target prioritization methods, shortest path and diffusion correlation. In addition, we validated the proportion of perturbed genes in clusters by finding candidate anti-breast cancer drugs and confirming our predictions using literature evidence and cases in the ClinicalTrials.gov. Our results indicate that the Walktrap (CW) clustering algorithm achieved the best performance overall in our comparative study.

Fake news on Twitter during the 2016 U.S. presidential election

The spread of fake news on social media became a public concern in the United States after the 2016 presidential election. We examined exposure to and sharing of fake news by registered voters on Twitter and found that engagement with fake news sources was extremely concentrated. Only 1% of individuals accounted for 80% of fake news source exposures, and 0.1% accounted for nearly 80% of fake news sources shared. Individuals most likely to engage with fake news sources were conservative leaning, older, and highly engaged with political news. A cluster of fake news sources shared overlapping audiences on the extreme right, but for people across the political spectrum, most political news exposure still came from mainstream media outlets.

Co-Association Matrix-Based Multi-Layer Fusion for Community Detection in Attributed Networks

Community detection is a challenging task in attributed networks, due to the data inconsistency between network topological structure and node attributes. The problem of how to effectively and robustly fuse multi-source heterogeneous data plays an important role in community detection algorithms. Although some algorithms taking both topological structure and node attributes into account have been proposed in recent years, the fusion strategy is simple and usually adopts the linear combination method. As a consequence of this, the detected community structure is vulnerable to small variations of the input data. In order to overcome this challenge, we develop a novel two-layer representation to capture the latent knowledge from both topological structure and node attributes in attributed networks. Then, we propose a weighted co-association matrix-based fusion algorithm (WCMFA) to detect the inherent community structure in attributed networks by using multi-layer fusion strategies. It extends the community detection method from a single-view to a multi-view style, which is consistent with the thinking model of human beings. Experiments show that our method is superior to the state-of-the-art community detection algorithms for attributed networks.

NMLPA: Uncovering Overlapping Communities in Attributed Networks via a Multi-Label Propagation Approach

With the enrichment of the entity information in the real world, many networks with attributed nodes are proposed and studied widely. Community detection in these attributed networks is an essential task that aims to find groups where the intra-nodes are much more densely connected than the inter-nodes. However, many existing community detection methods in attributed networks do not distinguish overlapping communities from non-overlapping communities when designing algorithms. In this paper, we propose a novel and accurate algorithm called Node-similarity-based Multi-Label Propagation Algorithm (NMLPA) for detecting overlapping communities in attributed networks. NMLPA first calculates the similarity between nodes and then propagates multiple labels based on the network structure and the node similarity. Moreover, NMLPA uses a pruning strategy to keep the number of labels per node within a suitable range. Extensive experiments conducted on both synthetic and real-world networks show that our new method significantly outperforms state-of-the-art methods.

From free text to clusters of content in health records: an unsupervised graph partitioning approach

Electronic healthcare records contain large volumes of unstructured data in different forms. Free text constitutes a large portion of such data, yet this source of richly detailed information often remains under-used in practice because of a lack of suitable methodologies to extract interpretable content in a timely manner. Here we apply network-theoretical tools to the analysis of free text in Hospital Patient Incident reports in the English National Health Service, to find clusters of reports in an unsupervised manner and at different levels of resolution based directly on the free text descriptions contained within them. To do so, we combine recently developed deep neural network text-embedding methodologies based on paragraph vectors with multi-scale Markov Stability community detection applied to a similarity graph of documents obtained from sparsified text vector similarities. We showcase the approach with the analysis of incident reports submitted in Imperial College Healthcare NHS Trust, London. The multiscale community structure reveals levels of meaning with different resolution in the topics of the dataset, as shown by relevant descriptive terms extracted from the groups of records, as well as by comparing a posteriori against hand-coded categories assigned by healthcare personnel. Our content communities exhibit good correspondence with well-defined hand-coded categories, yet our results also provide further medical detail in certain areas as well as revealing complementary descriptors of incidents beyond the external classification. We also discuss how the method can be used to monitor reports over time and across different healthcare providers, and to detect emerging trends that fall outside of pre-existing categories.

Dynamic Cluster Formation Game for Attributed Graph Clustering

Besides the topological structure, there are additional information, i.e., node attributes, on top of the plain graphs. Usually, these systems can be well modeled by attributed graphs, where nodes represent component actors, a set of attributes describe users' portraits and edges indicate their connections. An elusive question associated with attributed graphs is to study how clusters with common internal properties form and evolve in real-world networked systems with great individual diversity, which leads to the so-called problem of attributed graph clustering (AGC). In this paper, we comprehended AGC naturally as a dynamic cluster formation game (DCFG), where each node's feasible action set can be constrained by every cluster in a discrete-time dynamical system. Specifically, we carried out a deep research on a special case of finite dynamic games, named dynamic social game (DSG), the convergence of the finite Nash equilibrium sequence in a DSG was also proved strictly. By carefully defining the feasible action set and the utility function associated with each node, the proposed DCFG can be well related to a DSG; and we showed that a balanced solution of AGC could be found by solving a finite set of coupled static Nash equilibrium problems in the related DCFG. We, finally, proposed a self-learning algorithm, which can start from any arbitrary initial cluster configuration, and, finally, find the corresponding balanced solution of AGC, where all nodes and clusters are satisfied with the final cluster configuration. Extensive experiments were applied on real-world social networks to demonstrate both effectiveness and scalability of the proposed approach by comparing with the state-of-the-art graph clustering methods in the literature.

On the Analysis of the Influence of the Evaluation Metric in Community Detection over Social Networks

Community detection in social networks is becoming one of the key tasks in social network analysis, since it helps with analyzing groups of users with similar interests. As a consequence, it is possible to detect radicalism or even reduce the size of the data to be analyzed, among other applications. This paper presents a metaheuristic approach based on Greedy Randomized Adaptive Search Procedure (GRASP) methodology for detecting communities in social networks. The community detection problem is modeled as an optimization problem, where the objective function to be optimized is the modularity of the network, a well-known metric in this scientific field. The results obtained outperform classical methods of community detection over a set of real-life instances with respect to the quality of the communities detected.

GOLAP: Graph-Based Online Analytical Processing

Graph-based Online Analytical Processing (GOLAP) extends Online Analytical Processing (OLAP) to address graph-based problems that involve object attributes. Based on graph data, GOLAP can answer user queries related to combinatorial optimization, structural analytics, and influence analytics. Besides, since a GOLAP system is an online interactive system that requires fast response time, the execution time for graph-problem queries is essentially critical. Thus, how to speed up the execution time of specific graph problems becomes a challenge in GOLAP. In this paper, we show several methods to speed up the running time, including graph data reduction and approximation. In this paper, we survey classes of graph-based queries, challenges for GOLAP, and solutions that GOLAP provides.

Network partitioning algorithms as cooperative games

The paper is devoted to game-theoretic methods for community detection in networks. The traditional methods for detecting community structure are based on selecting dense subgraphs inside the network. Here we propose to use the methods of cooperative game theory that highlight not only the link density but also the mechanisms of cluster formation. Specifically, we suggest two approaches from cooperative game theory: the first approach is based on the Myerson value, whereas the second approach is based on hedonic games. Both approaches allow to detect clusters with various resolutions. However, the tuning of the resolution parameter in the hedonic games approach is particularly intuitive. Furthermore, the modularity-based approach and its generalizations as well as ratio cut and normalized cut methods can be viewed as particular cases of the hedonic games. Finally, for approaches based on potential hedonic games we suggest a very efficient computational scheme using Gibbs sampling.

Multiresolution Network Models

Many existing statistical and machine learning tools for social network analysis focus on a single level of analysis. Methods designed for clustering optimize a global partition of the graph, whereas projection-based approaches (e.g., the latent space model in the statistics literature) represent in rich detail the roles of individuals. Many pertinent questions in sociology and economics, however, span multiple scales of analysis. Further, many questions involve comparisons across disconnected graphs that will, inevitably be of different sizes, either due to missing data or the inherent heterogeneity in real-world networks. We propose a class of network models that represent network structure on multiple scales and facilitate comparison across graphs with different numbers of individuals. These models differentially invest modeling effort within subgraphs of high density, often termed communities, while maintaining a parsimonious structure between said subgraphs. We show that our model class is projective, highlighting an ongoing discussion in the social network modeling literature on the dependence of inference paradigms on the size of the observed graph. We illustrate the utility of our method using data on household relations from Karnataka, India. Supplementary material for this article is available online.

New approaches to pharmacosurveillance for monitoring prescription frequency, diversity, and co-prescription in a large sentinel network of companion animal veterinary practices in the United Kingdom, 2014-2016

Pharmaceutical agents (PAs) are commonly prescribed in companion animal practice in the United Kingdom. However, little is known about PA prescription on a population-level, particularly with respect to PAs authorised for human use alone prescribed via the veterinary cascade; this raises important questions regarding the efficacy and safety of PAs prescribed to companion animals. This study explored new approaches for describing PA prescription, diversity and co-prescription in dogs, cats and rabbits utilising electronic health records (EHRs) from a sentinel network of 457 companion animal-treating veterinary sites throughout the UK over a 2-year period (2014-2016). A novel text mining-based identification and classification methodology was utilised to semi-automatically map practitioner-defined product descriptions recorded in 918,333 EHRs from 413,870 dogs encompassing 1,242,270 prescriptions; 352,730 EHRs from 200,541 cats encompassing 491,554 prescriptions, and 22,526 EHRS from 13,398 rabbits encompassing 18,490 prescriptions respectively. PA prescription as a percentage of booked consultations was 65.4% (95% confidence interval, CI, 64.6-66.3) in dogs; in cats it was 69.1% (95% CI, 67.9-70.2) and in rabbits, 56.3% (95% CI, 54.7-57.8). Vaccines were the most commonly prescribed PAs in all three species, with antibiotics, antimycotics, and parasiticides also commonly prescribed. PA prescription utilising products authorised for human use only (hence, 'human-authorised') comprised 5.1% (95% CI, 4.7-5.5) of total canine prescription events; in cats it was 2.8% (95% CI, 2.6-3.0), and in rabbits, 7.8% (95% CI, 6.5-9.0). The most commonly prescribed human-authorised PA in dogs was metronidazole (antibiotic); in cats and rabbits it was ranitidine (H2 histamine receptor antagonist). Using a new approach utilising the Simpson's Diversity Index (an ecological measure of relative animal, plant etc. species abundance), we identified differences in prescription based on presenting complaint and species, with rabbits generally exposed to a less diverse range of PAs than dogs or cats, potentially reflecting the paucity of authorised PAs for use in rabbits. Finally, through a novel application of network analysis, we demonstrated the existence of three major co-prescription groups (preventive health; treatment of disease, and euthanasia); a trend commonly observed in practice. This study represents the first time PA prescription has been described across all pharmaceutical families in a large population of companion animals, encompassing PAs authorised for both veterinary and human-only use. These data form a baseline against which future studies could be compared, and provides some useful tools for understanding PA comparative efficacy and risks when prescribed in the varied setting of clinical practice.

Estimating Graph Robustness Through the Randic Index

Graph robustness-the ability of a graph to preserve its connectivity after the loss of nodes and edges-has been extensively studied to quantify how social, biological, physical, and technical systems withstand to external damages. In this paper, we prove that graph robustness can be quickly estimated through the Randic index, a parameter introduced in chemistry to study organic compounds. We prove that Erdos-Renyj (ER) graphs are a good specimen of robust graphs because they lack of a clear modular structure; we derive an analytical expression for the Randic index of ER graphs and use ER graphs as an effective term of comparison to decide about graph robustness. Experiments on real datasets from different domains (scientific collaboration networks, content-sharing systems, co-purchase networks from an e-commerce platform, and a road network) show that real-life large graphs are more robust than ER ones with the same number of nodes and edges. We also observe that if node degree distribution closely follows a power law, then few edges contribute for more than half of the Randic index, thus indicating that the selective removal of those edges has devastating impact on graph robustness. Finally, we describe sampling-based algorithms to efficiently but accurately approximate the Randic index.

Global vs local modularity for network community detection

Community structures are ubiquitous in various complex networks, implying that the networks commonly be composed of groups of nodes with more internal links and less external links. As an important topic in network theory, community detection is of importance for understanding the structure and function of the networks. Optimizing statistical measures for community structures is one of most popular strategies for community detection in complex networks. In the paper, by using a type of self-loop rescaling strategy, we introduced a set of global modularity functions and a set of local modularity functions for community detection in networks, which are optimized by a kind of the self-consistent method. We carefully compared and analyzed the behaviors of the modularity-based methods in community detection, and confirmed the superiority of the local modularity for detecting community structures on large-size and heterogeneous networks. The local modularity can more quickly eliminate the first-type limit of modularity, and can eliminate or alleviate the second-type limit of modularity in networks, because of the use of the local information in networks. Moreover, we tested the methods in real networks. Finally, we expect the research can provide useful insight into the problem of community detection in complex networks.

wTO: an R package for computing weighted topological overlap and a consensus network with integrated visualization tool

BACKGROUND

Network analyses, such as of gene co-expression networks, metabolic networks and ecological networks have become a central approach for the systems-level study of biological data. Several software packages exist for generating and analyzing such networks, either from correlation scores or the absolute value of a transformed score called weighted topological overlap (wTO). However, since gene regulatory processes can up- or down-regulate genes, it is of great interest to explicitly consider both positive and negative correlations when constructing a gene co-expression network.

RESULTS

Here, we present an R package for calculating the weighted topological overlap (wTO), that, in contrast to existing packages, explicitly addresses the sign of the wTO values, and is thus especially valuable for the analysis of gene regulatory networks. The package includes the calculation of p-values (raw and adjusted) for each pairwise gene score. Our package also allows the calculation of networks from time series (without replicates). Since networks from independent datasets (biological repeats or related studies) are not the same due to technical and biological noise in the data, we additionally, incorporated a novel method for calculating a consensus network (CN) from two or more networks into our R package. To graphically inspect the resulting networks, the R package contains a visualization tool, which allows for the direct network manipulation and access of node and link information. When testing the package on a standard laptop computer, we can conduct all calculations for systems of more than 20,000 genes in under two hours. We compare our new wTO package to state of art packages and demonstrate the application of the wTO and CN functions using 3 independently derived datasets from healthy human pre-frontal cortex samples. To showcase an example for the time series application we utilized a metagenomics data set.

CONCLUSION

In this work, we developed a software package that allows the computation of wTO networks, CNs and a visualization tool in the R statistical environment. It is publicly available on CRAN repositories under the GPL -2 Open Source License ( https://cran.r-project.org/web/packages/wTO/ ).

Metanetwork Transmission Model for Predicting a Malaria-Control Strategy

Background: Mosquitoes are the primary vectors responsible for malaria transmission to humans, with numerous experiments having been conducted to aid in the control of malaria transmission. One of the main approaches aims to develop malaria parasite resistance within the mosquito population by introducing a resistance (R) allele. However, when considering this approach, some critical factors, such as the life of the mosquito, female mosquito fertility capacity, and human and mosquito mobility, have not been considered. Thus, an understanding of how mosquitoes and humans affect disease dynamics is needed to better inform malaria control policymaking. Methods: In this study, a method was proposed to create a metanetwork on the basis of the geographic maps of Gambia, and a model was constructed to simulate evolution within a mixed population, with factors such as birth, death, reproduction, biting, infection, incubation, recovery, and transmission between populations considered in the network metrics. First, the same number of refractory mosquitoes (RR genotype) was introduced into each population, and the prevalence of the R allele (the ratio of resistant alleles to all alleles) and malaria were examined. In addition, a series of simulations were performed to evaluate two different deployment strategies for the reduction of the prevalence of malaria. The R allele and malaria prevalence were calculated for both the strategies, with 10,000 refractory mosquitoes deployed into randomly selected populations or selection based on nodes with top-betweenness values. The 10,000 mosquitoes were deployed among 1, 5, 10, 20, or 40 populations. Results: The simulations in this paper showed that a higher RR genotype (resistant-resistant genes) ratio leads to a higher R allele prevalence and lowers malaria prevalence. Considering the cost of deployment, the simulation was performed with 10,000 refractory mosquitoes deployed among 1 or 5 populations, but this approach did not reduce the original malaria prevalence. Thus, instead, the 10,000 refractory mosquitoes were distributed among 10, 20, or 40 populations and were shown to effectively reduce the original malaria prevalence. Thus, deployment among a relatively small fraction of central nodes can offer an effective strategy to reduce malaria. Conclusion: The standard network centrality measure is suitable for planning the deployment of refractory mosquitoes. Importance: Malaria is an infectious disease that is caused by a plasmodial parasite, and some control strategies have focused on genetically modifying the mosquitoes. This work aims to create a model that takes into account mosquito development and malaria transmission among the population and how these factors influence disease dynamics so as to better inform malaria-control policymaking.

A Network Pharmacology Approach to Uncover the Molecular Mechanisms of Herbal Formula Ban-Xia-Xie-Xin-Tang

Ban-Xia-Xie-Xin-Tang (BXXXT) is a classical formula from Shang-Han-Lun which is one of the earliest books of TCM clinical practice. In this work, we investigated the therapeutic mechanisms of BXXXT for the treatment of multiple diseases using a network pharmacology approach. Here three BXXXT representative diseases (colitis, diabetes mellitus, and gastric cancer) were discussed, and we focus on in silico methods that integrate drug-likeness screening, target prioritizing, and multilayer network extending. A total of 140 core targets and 72 representative compounds were finally identified to elucidate the pharmacology of BXXXT formula. After constructing multilayer networks, a good overlap between BXXXT nodes and disease nodes was observed at each level, and the network-based proximity analysis shows that the relevance between the formula targets and disease genes was significant according to the shortest path distance (SPD) and a random walk with restart (RWR) based scores for each disease. We found that there were 22 key pathways significantly associated with BXXXT, and the therapeutic effects of BXXXT were likely addressed by regulating a combination of targets in a modular pattern. Furthermore, the synergistic effects among BXXXT herbs were highlighted by elucidating the molecular mechanisms of individual herbs, and the traditional theory of "Jun-Chen-Zuo-Shi" of TCM formula was effectively interpreted from a network perspective. The proposed approach provides an effective strategy to uncover the mechanisms of action and combinatorial rules of BXXXT formula in a holistic manner.

A Central Edge Selection Based Overlapping Community Detection Algorithm for the Detection of Overlapping Structures in Protein⁻Protein Interaction Networks

Overlapping structures of protein⁻protein interaction networks are very prevalent in different biological processes, which reflect the sharing mechanism to common functional components. The overlapping community detection (OCD) algorithm based on central node selection (CNS) is a traditional and acceptable algorithm for OCD in networks. The main content of CNS is the central node selection and the clustering procedure. However, the original CNS does not consider the influence among the nodes and the importance of the division of the edges in networks. In this paper, an OCD algorithm based on a central edge selection (CES) algorithm for detection of overlapping communities of protein⁻protein interaction (PPI) networks is proposed. Different from the traditional CNS algorithms for OCD, the proposed algorithm uses community magnetic interference (CMI) to obtain more reasonable central edges in the process of CES, and employs a new distance between the non-central edge and the set of the central edges to divide the non-central edge into the correct cluster during the clustering procedure. In addition, the proposed CES improves the strategy of overlapping nodes pruning (ONP) to make the division more precisely. The experimental results on three benchmark networks and three biological PPI networks of Mus. musculus, Escherichia coli, and Cerevisiae show that the CES algorithm performs well.

Global-scale phylogenetic linguistic inference from lexical resources

Automatic phylogenetic inference plays an increasingly important role in computational historical linguistics. Most pertinent work is currently based on expert cognate judgments. This limits the scope of this approach to a small number of well-studied language families. We used machine learning techniques to compile data suitable for phylogenetic inference from the ASJP database, a collection of almost 7,000 phonetically transcribed word lists over 40 concepts, covering two thirds of the extant world-wide linguistic diversity. First, we estimated Pointwise Mutual Information scores between sound classes using weighted sequence alignment and general-purpose optimization. From this we computed a dissimilarity matrix over all ASJP word lists. This matrix is suitable for distance-based phylogenetic inference. Second, we applied cognate clustering to the ASJP data, using supervised training of an SVM classifier on expert cognacy judgments. Third, we defined two types of binary characters, based on automatically inferred cognate classes and on sound-class occurrences. Several tests are reported demonstrating the suitability of these characters for character-based phylogenetic inference.

Energy Efficient Hybrid Routing Protocol Based on the Artificial Fish Swarm Algorithm and Ant Colony Optimisation for WSNs

Wireless Sensor Networks (WSNs) are a particular type of distributed self-managed network with limited energy supply and communication ability. The most significant challenge of a routing protocol is the energy consumption and the extension of the network lifetime. Many energy-efficient routing algorithms were inspired by the development of Ant Colony Optimisation (ACO). However, due to the inborn defects, ACO-based routing algorithms have a slow convergence behaviour and are prone to premature, stagnation phenomenon, which hinders further route discovery, especially in a large-scale network. This paper proposes a hybrid routing algorithm by combining the Artificial Fish Swarm Algorithm (AFSA) and ACO to address these issues. We utilise AFSA to perform the initial route discovery in order to find feasible routes quickly. In the route discovery algorithm, we present a hybrid algorithm by combining the crowd factor in AFSA and the pseudo-random route select strategy in ACO. Furthermore, this paper presents an improved pheromone update method by considering energy levels and path length. Simulation results demonstrate that the proposed algorithm avoids the routing algorithm falling into local optimisation and stagnation, whilst speeding up the routing convergence, which is more prominent in a large-scale network. Furthermore, simulation evaluation reports that the proposed algorithm exhibits a significant improvement in terms of network lifetime.

Polarization of the vaccination debate on Facebook

BACKGROUND

Vaccine hesitancy has been recognized as a major global health threat. Having access to any type of information in social media has been suggested as a potential influence on the growth of anti-vaccination groups. Recent studies w.r.t. other topics than vaccination show that access to a wide amount of content through the Internet without intermediaries resolved into major segregation of the users in polarized groups. Users select information adhering to theirs system of beliefs and tend to ignore dissenting information.

OBJECTIVES

The goal was to assess whether users' attitudes are polarized on the topic of vaccination on Facebook and how this polarization develops over time.

METHODS

We perform a thorough quantitative analysis by studying the interaction of 2.6 M users with 298,018 Facebook posts over a time span of seven years and 5 months. We applied community detection algorithms to automatically detect the emergence of communities accounting for the users' activity on the pages. Also, we quantified the cohesiveness of these communities over time.

RESULTS

Our findings show that the consumption of content about vaccines is dominated by the echo chamber effect and that polarization increased over the years. Well-segregated communities emerge from the users' consumption habits i.e., the majority of users consume information in favor or against vaccines, not both.

CONCLUSION

The existence of echo chambers may explain why social-media campaigns that provide accurate information have limited reach and be effective only in sub-groups, even fomenting further opinion polarization. The introduction of dissenting information into a sub-group is disregarded and can produce a backfire effect, thus reinforcing the pre-existing opinions within the sub-group. Public health professionals should try to understand the contents of these echo chambers, for example by getting passively involved in such groups. Only then it will be possible to find effective ways of countering anti-vaccination thinking.

Proactive Caching at the Edge Leveraging Influential User Detection in Cellular D2D Networks

Caching close to users in a radio access network (RAN) has been identified as a promising method to reduce a backhaul traffic load and minimize latency in 5G and beyond. In this paper, we investigate a novel community detection inspired by a proactive caching scheme for device-to-device (D2D) enabled networks. The proposed scheme builds on the idea that content generated/accessed by influential users is more probable to become popular and thus can be exploited for pro-caching. We use a Clustering Coefficient based Genetic Algorithm (CC-GA) for community detection to discover a group of cellular users present in close vicinity. We then use an Eigenvector Centrality measure to identify the influential users with respect to the community structure, and the content associated to it is then used for pro-active caching using D2D communications. The numerical results show that, compared to reactive caching, where historically popular content is cached, depending on cache size, load and number of requests, up to 30% more users can be satisfied using a proposed scheme while achieving significant reduction in backhaul traffic load.

Lossy Graph Data Reduction

Graphs are widely used nowadays to store complex data of large applications such as social networks, recommendation engines, computer networks, bio-informatics, just to name a few. Graph data reduction plays a very important role in order to store and process such data efficiently. Many studies about graph data reduction have been done, but most of them are focused on lossless reduction in the sense that query results are preserved after reduction. In this paper, we elaborate on the concept of “lossy” graph reduction for applications that may tolerate approximate results with small but bounded errors in exchange for further data reduction. We study one well known graph problem that is the shortest path problem and design the lossy graph reduction algorithms. The error bounds of the algorithms we propose are proved theoretically. In addition, we implement some of the algorithms based on real world data sets to experimentally investigate the impacts of the error tolerance on the reduction ratio.

Mind the Gap: Mapping Mass Spectral Databases in Genome-Scale Metabolic Networks Reveals Poorly Covered Areas

The use of mass spectrometry-based metabolomics to study human, plant and microbial biochemistry and their interactions with the environment largely depends on the ability to annotate metabolite structures by matching mass spectral features of the measured metabolites to curated spectra of reference standards. While reference databases for metabolomics now provide information for hundreds of thousands of compounds, barely 5% of these known small molecules have experimental data from pure standards. Remarkably, it is still unknown how well existing mass spectral libraries cover the biochemical landscape of prokaryotic and eukaryotic organisms. To address this issue, we have investigated the coverage of 38 genome-scale metabolic networks by public and commercial mass spectral databases, and found that on average only 40% of nodes in metabolic networks could be mapped by mass spectral information from standards. Next, we deciphered computationally which parts of the human metabolic network are poorly covered by mass spectral libraries, revealing gaps in the eicosanoids, vitamins and bile acid metabolism. Finally, our network topology analysis based on the betweenness centrality of metabolites revealed the top 20 most important metabolites that, if added to MS databases, may facilitate human metabolome characterization in the future.

Exploring the Hierarchical Structure of China’s Railway Network from 2008 to 2017

The analysis of transport networks is an important component of urban and regional development and planning. Based on the four main stages of China’s railway development from 2008 to 2017, this paper analyzes the hierarchical and spatial heterogeneity distribution of train flows. We found a high degree of spatial matching with the distribution of China’s main railway corridors. Then, using a classical community detection algorithm, this paper attempts to describe the functional structure and regional effects of China’s railway network. We also explore the impacts of construction policies and changes to train operations on the spatial organizing pattern and evolution of network hierarchies. The results of this empirical study reveal a clear pattern of independent communities, which in turn indicates the existence of a hierarchical structure in China’s railway network. The decreases in both the number of communities and average distance between community centers indicate that the newer high-speed rail services have shortened the connections between cities. In addition, the detected communities are inconsistent with China’s actual administrative divisions in terms of quantity and boundaries. The spatial spillover and segmentation effects cause the railway network in different regions to be self-contained. Finally, the detected communities in each stage can be divided into the categories of monocentric structure, dual-nuclei structure, and polycentric structure according to the number of extracted hubs. The polycentric structure is the dominant mode, which shows that the railway network has significant spatial dependence and a diversified spatial organization mode. This study has great significance for policymakers seeking to guide the future construction of high-speed rail lines and optimize national or regional railway networks.

Diffusion of User Tracking Data in the Online Advertising Ecosystem

Advertising and Analytics (A&A) companies have started collaborating more closely with one another due to the shift in the online advertising industry towards Real Time Bidding (RTB). One natural way to understand how user tracking data moves through this interconnected advertising ecosystem is by modeling it as a graph. In this paper, we introduce a novel graph representation, called an Inclusion graph, to model the impact of RTB on the diffusion of user tracking data in the advertising ecosystem. Through simulations on the Inclusion graph, we provide upper and lower estimates on the tracking information observed by A&A companies. We find that 52 A&A companies observe at least 91% of an average user’s browsing history under reasonable assumptions about information sharing within RTB auctions. We also evaluate the effectiveness of blocking strategies (e.g., AdBlock Plus), and find that major A&A companies still observe 40–90% of user impressions, depending on the blocking strategy.

Structure and consistency of self-reported social contact networks in British secondary schools

Self-reported social mixing patterns are commonly used in mathematical models of infectious diseases. It is particularly important to quantify patterns for school-age children given their disproportionate role in transmission, but it remains unclear how the structure of such social interactions changes over time. By integrating data collection into a public engagement programme, we examined self-reported contact networks in year 7 groups in four UK secondary schools. We collected data from 460 unique participants across four rounds of data collection conducted between January and June 2015, with 7,315 identifiable contacts reported in total. Although individual-level contacts varied over the study period, we were able to obtain out-of-sample accuracies of more than 90% and F-scores of 0.49-0.84 when predicting the presence or absence of social contacts between specific individuals across rounds of data collection. Network properties such as clustering and number of communities were broadly consistent within schools between survey rounds, but varied significantly between schools. Networks were assortative according to gender, and to a lesser extent school class, with the estimated clustering coefficient larger among males in all surveyed co-educational schools. Our results demonstrate that it is feasible to collect longitudinal self-reported social contact data from school children and that key properties of these data are consistent between rounds of data collection.

Different Anti-Vaping Campaigns Attracting the Same Opponent Community

E-cigarettes (vape) are now the most commonly used tobacco product among youth in the United States. Ads are claiming e-cigarettes help smokers quit, but most of them contain nicotine, which can cause addiction and harm the developing adolescent brain. Therefore, national, state, and local health organizations have proposed anti-vaping campaigns to warn the potential risks of e-cigarettes. However, there is some evidence that these products may reduce harm for adult users who reduce or quit combustible cigarette smoking, and with little evidence that e-cigarettes cause long-term harm, pro-vaping advocates have used this equivocal evidence base to oppose the anti-vaping media campaign messaging, generating a very high volume of oppositional messages on social media. Thus, when we analyze the feedback of anti-vaping campaigns, it is crucial to partition the audience into different clusters according to their attitudes and affiliations. Motivated by this, in this paper, we propose the "community detection on anti-vaping campaign audience" problem and design the "community detection based on social, repost and content relation, (Sorento)" algorithm to solve it. Sorento computes users' intimacy scores based on their social connections, repost relations, and content similarities. The community detection results achieved by Sorento demonstrate that though anti-vaping campaigns are proposed in different areas at different times, their opponent messages are mainly posted by the same community of pro-vapors.

Coupled Node Similarity Learning for Community Detection in Attributed Networks

Attributed networks consist of not only a network structure but also node attributes. Most existing community detection algorithms only focus on network structures and ignore node attributes, which are also important. Although some algorithms using both node attributes and network structure information have been proposed in recent years, the complex hierarchical coupling relationships within and between attributes, nodes and network structure have not been considered. Such hierarchical couplings are driving factors in community formation. This paper introduces a novel coupled node similarity (CNS) to involve and learn attribute and structure couplings and compute the similarity within and between nodes with categorical attributes in a network. CNS learns and integrates the frequency-based intra-attribute coupled similarity within an attribute, the co-occurrence-based inter-attribute coupled similarity between attributes, and coupled attribute-to-structure similarity based on the homophily property. CNS is then used to generate the weights of edges and transfer a plain graph to a weighted graph. Clustering algorithms detect community structures that are topologically well-connected and semantically coherent on the weighted graphs. Extensive experiments verify the effectiveness of CNS-based community detection algorithms on several data sets by comparing with the state-of-the-art node similarity measures, whether they involve node attribute information and hierarchical interactions, and on various levels of network structure complexity.