Dynamic Cluster Formation Game for Attributed Graph Clustering

Smoothness Sensor: Adaptive Smoothness-Transition Graph Convolutions for Attributed Graph Clustering

Clustering techniques attempt to group objects with similar properties into a cluster. Clustering the nodes of an attributed graph, in which each node is associated with a set of feature attributes, has attracted significant attention. Graph convolutional networks (GCNs) represent an effective approach for integrating the two complementary factors of node attributes and structural information for attributed graph clustering. Smoothness is an indicator for assessing the degree of similarity of feature representations among nearby nodes in a graph. Oversmoothing in GCNs, caused by unnecessarily high orders of graph convolution, produces indistinguishable representations of nodes, such that the nodes in a graph tend to be grouped into fewer clusters, and pose a challenge due to the resulting performance drop. In this study, we propose a smoothness sensor for attributed graph clustering based on adaptive smoothness-transition graph convolutions, which senses the smoothness of a graph and adaptively terminates the current convolution once the smoothness is saturated to prevent oversmoothing. Furthermore, as an alternative to graph-level smoothness, a novel fine-grained nodewise-level assessment of smoothness is proposed, in which smoothness is computed in accordance with the neighborhood conditions of a given node at a certain order of graph convolution. In addition, a self-supervision criterion is designed considering both the tightness within clusters and the separation between clusters to guide the entire neural network training process. The experiments show that the proposed methods significantly outperform 13 other state-of-the-art baselines in terms of different metrics across five benchmark datasets. In addition, an extensive study reveals the reasons for their effectiveness and efficiency.

Contextual Correlation Preserving Multiview Featured Graph Clustering

Graph clustering, which aims at discovering sets of related vertices in graph-structured data, plays a crucial role in various applications, such as social community detection and biological module discovery. With the huge increase in the volume of data in recent years, graph clustering is used in an increasing number of real-life scenarios. However, the classical and state-of-the-art methods, which consider only single-view features or a single vector concatenating features from different views and neglect the contextual correlation between pairwise features, are insufficient for the task, as features that characterize vertices in a graph are usually from multiple views and the contextual correlation between pairwise features may influence the cluster preference for vertices. To address this challenging problem, we introduce in this paper, a novel graph clustering model, dubbed contextual correlation preserving multiview featured graph clustering (CCPMVFGC) for discovering clusters in graphs with multiview vertex features. Unlike most of the aforementioned approaches, CCPMVFGC is capable of learning a shared latent space from multiview features as the cluster preference for each vertex and making use of this latent space to model the inter-relationship between pairwise vertices. CCPMVFGC uses an effective method to compute the degree of contextual correlation between pairwise vertex features and utilizes view-wise latent space representing the feature-cluster preference to model the computed correlation. Thus, the cluster preference learned by CCPMVFGC is jointly inferred by multiview features, view-wise correlations of pairwise features, and the graph topology. Accordingly, we propose a unified objective function for CCPMVFGC and develop an iterative strategy to solve the formulated optimization problem. We also provide the theoretical analysis of the proposed model, including convergence proof and computational complexity analysis. In our experiments, we extensively compare the proposed CCPMVFGC with both classical and state-of-the-art graph clustering methods on eight standard graph datasets (six multiview and two single-view datasets). The results show that CCPMVFGC achieves competitive performance on all eight datasets, which validates the effectiveness of the proposed model.

Community detection with node attributes in multilayer networks

Community detection in networks is commonly performed using information about interactions between nodes. Recent advances have been made to incorporate multiple types of interactions, thus generalizing standard methods to multilayer networks. Often, though, one can access additional information regarding individual nodes, attributes, or covariates. A relevant question is thus how to properly incorporate this extra information in such frameworks. Here we develop a method that incorporates both the topology of interactions and node attributes to extract communities in multilayer networks. We propose a principled probabilistic method that does not assume any a priori correlation structure between attributes and communities but rather infers this from data. This leads to an efficient algorithmic implementation that exploits the sparsity of the dataset and can be used to perform several inference tasks; we provide an open-source implementation of the code online. We demonstrate our method on both synthetic and real-world data and compare performance with methods that do not use any attribute information. We find that including node information helps in predicting missing links or attributes. It also leads to more interpretable community structures and allows the quantification of the impact of the node attributes given in input.

Role of vaccine efficacy in the vaccination behavior under myopic update rule on complex networks

How to effectively prevent the diffusion of infectious disease has become an intriguing topic in the field of public hygienics. To be noted that, for the non-periodic infectious diseases, many people hope to obtain the vaccine of epidemics in time to be inoculated, rather than at the end of the epidemic. However, the vaccine may fail as a result of invalid storage, transportation and usage, and then vaccinated individuals may become re-susceptible and be infected again during the outbreak. To this end, we build a new framework that considers the imperfect vaccination during the one cycle of infectious disease within the spatially structured and heterogeneous population. Meanwhile, we propose a new vaccination update rule: myopic update rule, which is only based on one focal player's own perception regarding the disease outbreak, and one susceptible individual makes a decision to adopt the vaccine just by comparing the perceived payoffs vaccination with the perceived ones of being infected. Extensive Monte-Carlo simulations are performed to demonstrate the imperfect vaccination behavior under the myopic update rule in the spatially structured and heterogeneous population. The results indicate that healthy individuals are often willing to inoculate the vaccine under the myopic update rule, which can stop the infectious disease from being spread, in particular, it is found that the vaccine efficacy influences the fraction of vaccinated individuals much more than the relative cost of vaccination on the regular lattice, Meanwhile, vaccine efficacy is more sensitive on the heterogeneous scale-free network. Current results are helpful to further analyze and model the choice of vaccination strategy during the disease outbreaks.

A new grid- and modularity-based layout algorithm for complex biological networks

The visualization of biological networks is critically important to aid researchers in understanding complex biological systems and arouses interest in designing efficient layout algorithms to draw biological networks according to their topology structures, especially for those networks with potential modules. The algorithms of grid layout series have an advantage in generating compact layouts with overlap-free nodes compared to force-directed; however, extant grid layout algorithms have difficulty in drawing modular networks and often generate layouts of high visual complexity when applied to networks with dense or clustered connectivity structure. To specifically assist the study of modular networks, we propose a grid- and modularity-based layout algorithm (GML) that consists of three stages: network preprocessing, module layout and grid optimization. The algorithm can draw complex biological networks with or without predefined modules based on the grid layout algorithm. It also outperforms other existing grid-based algorithms in the measurement of computation performance, ratio of edge-edge/node-edge crossings, relative edge lengths, and connectivity F-measures. GML helps users to gain insight into the network global characteristics through module layout, as well as to discern network details with grid optimization. GML has been developed as a VisANT plugin (https://hscz.github.io/Biological-Network-Visualization/) and is freely available to the research community.

A Scheme to Design Community Detection Algorithms in Various Networks

Network structures, consisting of nodes and edges, have applications in almost all subjects. A set of nodes is called a community if the nodes have strong interrelations. Industries (including cell phone carriers and online social media companies) need community structures to allocate network resources and provide proper and accurate services. However, most detection algorithms are derived independently, which is arduous and even unnecessary. Although recent research shows that a general detection method that serves all purposes does not exist, we believe that there is some general procedure of deriving detection algorithms. In this paper, we represent such a general scheme. We mainly focus on two types of networks: transmission networks and similarity networks. We reduce them to a unified graph model, based on which we propose a method to define and detect community structures. Finally, we also give a demonstration to show how our design scheme works.

Stability Analysis for Memristor-Based Complex-Valued Neural Networks with Time Delays

In this paper, the problem of stability analysis for memristor-based complex-valued neural networks (MCVNNs) with time-varying delays is investigated extensively. This paper focuses on the exponential stability of the MCVNNs with time-varying delays. By means of the Brouwer's fixed-point theorem and M-matrix, the existence, uniqueness, and exponential stability of the equilibrium point for MCVNNs are studied, and several sufficient conditions are obtained. In particular, these results can be applied to general MCVNNs whether the activation functions could be explicitly described by dividing into two parts of the real parts and imaginary parts or not. Two numerical simulation examples are provided to illustrate the effectiveness of the theoretical results.