How Symmetric Are Real-World Graphs? A Large-Scale Study

The transition to synchronization of networked systems

We study the synchronization properties of a generic networked dynamical system, and show that, under a suitable approximation, the transition to synchronization can be predicted with the only help of eigenvalues and eigenvectors of the graph Laplacian matrix. The transition comes out to be made of a well defined sequence of events, each of which corresponds to a specific clustered state. The network's nodes involved in each of the clusters can be identified, and the value of the coupling strength at which the events are taking place can be approximately ascertained. Finally, we present large-scale simulations which show the accuracy of the approximation made, and of our predictions in describing the synchronization transition of both synthetic and real-world large size networks, and we even report that the observed sequence of clusters is preserved in heterogeneous networks made of slightly non-identical systems.

Exploration of the optimal modularity in assembly line design

It is widely accepted that a proper structural modularity degree of assembly processes in terms of mass customization has a positive effect on their efficiency because it, among other things, increases manufacturing flexibility and productivity. On the other hand, most practical approaches to identify such a degree is rather based on intuition or analytical reasoning than on scientific foundations. However, the first way can be used for simple assembly tasks, but in more complex assembly processes, this method lags behind the second. The purpose was to create a methodology for selection of optimal modular assembly model from among a predefined set of alternatives. The methodology is based on exploration of the relations between modularity measures and complexity issues as well as the relationship between structural modularity and symmetry. Especially, the linkage between modularity and complexity properties has been explored in order to show how modularization can affect distribution of the total structural complexity across the entire assembly line. To solve this selection problem, three different methods are preliminary suggested and compared via a series of numerical tests. The two of them present the novel contribution of this work, while the third method developed earlier for the purpose of finding and evaluating community structure in networks was adapted for a given application domain. Based on obtained results, one of these method is prioritized over another, since it offers more promising results and precision too.

Distance-based clustering challenges for unbiased benchmarking studies

Benchmark datasets with predefined cluster structures and high-dimensional biomedical datasets outline the challenges of cluster analysis: clustering algorithms are limited in their clustering ability in the presence of clusters defining distance-based structures resulting in a biased clustering solution. Data sets might not have cluster structures. Clustering yields arbitrary labels and often depends on the trial, leading to varying results. Moreover, recent research indicated that all partition comparison measures can yield the same results for different clustering solutions. Consequently, algorithm selection and parameter optimization by unsupervised quality measures (QM) are always biased and misleading. Only if the predefined structures happen to meet the particular clustering criterion and QM, can the clusters be recovered. Results are presented based on 41 open-source algorithms which are particularly useful in biomedical scenarios. Furthermore, comparative analysis with mirrored density plots provides a significantly more detailed benchmark than that with the typically used box plots or violin plots.

Dimension-reduction of dynamics on real-world networks with symmetry

We derive explicit formulae to quantify the Markov chain state-space compression, or lumping, that can be achieved in a broad range of dynamical processes on real-world networks, including models of epidemics and voting behaviour, by exploiting redundancies due to symmetries. These formulae are applied in a large-scale study of such symmetry-induced lumping in real-world networks, from which we identify specific networks for which lumping enables exact analysis that could not have been done on the full state-space. For most networks, lumping gives a state-space compression ratio of up to 10 7 , but the largest compression ratio identified is nearly 10 12 . Many of the highest compression ratios occur in animal social networks. We also present examples of types of symmetry found in real-world networks that have not been previously reported.

Exact Maximal Reduction Of Stochastic Reaction Networks By Species Lumping

MOTIVATION

Stochastic reaction networks are a widespread model to describe biological systems where the presence of noise is relevant, such as in cell regulatory processes. Unfortunately, in all but simplest models the resulting discrete state-space representation hinders analytical tractability and makes numerical simulations expensive. Reduction methods can lower complexity by computing model projections that preserve dynamics of interest to the user.

RESULTS

We present an exact lumping method for stochastic reaction networks with mass-action kinetics. It hinges on an equivalence relation between the species, resulting in a reduced network where the dynamics of each macro-species is stochastically equivalent to the sum of the original species in each equivalence class, for any choice of the initial state of the system. Furthermore, by an appropriate encoding of kinetic parameters as additional species, the method can establish equivalences that do not depend on specific values of the parameters. The method is supported by an efficient algorithm to compute the largest species equivalence, thus the maximal lumping. The effectiveness and scalability of our lumping technique, as well as the physical interpretability of resulting reductions, is demonstrated in several models of signaling pathways and epidemic processes on complex networks.

AVAILABILITY

The algorithms for species equivalence have been implemented in the software tool ERODE, freely available for download from https://www.erode.eu.

A Symmetry-Breaking Node Equivalence for Pruning the Search Space in Backtracking Algorithms

We introduce a new equivalence on graphs, defined by its symmetry-breaking capability. We first present a framework for various backtracking search algorithms, in which the equivalence is used to prune the search tree. Subsequently, we define the equivalence and an optimization problem with the goal of finding an equivalence partition with the highest pruning potential. We also position the optimization problem into the computational-complexity hierarchy. In particular, we show that the verifier lies between P and NP -complete problems. Striving for a practical usability of the approach, we devise a heuristic method for general graphs and optimal algorithms for trees and cycles.

Analysis of Open Source Operating System Evolution: A Perspective from Package Dependency Network Motif

Complexity of open source operating systems constantly increase on account of their widespread application. It is increasingly difficult to understand the collaboration between components in the system. Extant research of open source operating system evolution is mainly achieved by Lehman’s law, which is conducted by analyzing characteristics such as line of the source code. Networks, which are utilized to demonstrate relationships among entities, is an adequate model for exploring cooperation of units that form a software system. Software network has become a research hotspot in the field of software engineering, leading to a new viewpoint for us to estimate evolution of open source operating systems. Motif, a connected subgraph that occurs frequently in a network, is extensively used in other scientific research such as bioscience to detect evolutionary rules. Thus, this paper constructs software package dependency network of open source software operating systems and investigates their evolutionary discipline from the perspective of the motif. Results of our experiments, which took Ubuntu Kylin as a study example, indicate a stable evolution of motif change as well as discovering structural defect in that system.

Package Network Model: A Way to Capture Holistic Structural Features of Open-Source Operating Systems

Open-source software has become a powerful engine for the development of the software industry. Its production mode, which is based on large-scale group collaboration, allows for the rapid and continuous evolution of open-source software on demand. As an important branch of open-source software, open-source operating systems are commonly used in modern service industries such as finance, logistics, education, medical care, e-commerce and tourism, etc. The reliability of these systems is increasingly valued. However, a self-organizing and loosely coupled development approach complicates the structural analysis of open-source operating system software. Traditional methods focus on analysis at the local level. There is a lack of research on the relationship between internal attributes and external overall characteristics. Consequently, conventional methods are difficult to adapt to complex software systems, especially the structural analysis of open-source operating system software. It is therefore of great significance to capture the holistic structure and behavior of the software system. Complex network theory, which is adequate for this task, can make up for the deficiency of traditional software structure evaluation methods that focus only on local structure. In this paper, we propose a package network model, which is a directed graph structure, to describe the dependency of open-source operating system software packages. Based on the Ubuntu Kylin Linux Operating system, we construct a software package dependency network of each distributed version and analyze the structural evolution through the dimensions of scale, density, connectivity, cohesion, and heterogeneity of each network.

IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem

The Symmetric Traveling Salesman Problem (sTSP) is an intensively studied NP-hard problem. It has many important real-life applications such as logistics, planning, manufacturing of microchips and DNA sequencing. In this paper we propose a cluster level incremental tour construction method called Intra-cluster Refinement Heuristic (IntraClusTSP). The proposed method can be used both to extend the tour with a new node and to improve the existing tour. The refinement step generates a local optimal tour for a cluster of neighbouring nodes and this local optimal tour is then merged into the global optimal tour. Based on the performed evaluation tests the proposed IntraClusTSP method provides an efficient incremental tour generation and it can improve the tour efficiency for every tested state-of-the-art methods including the most efficient Chained Lin-Kernighan refinement algorithm. As an application example, we apply IntraClusTSP to automatically determine the optimal number of clusters in a cluster analysis problem. The standard methods like Silhouette index, Elbow method or Gap statistic method, to estimate the number of clusters support only partitional (single level) clustering, while in many application areas, the hierarchical (multi-level) clustering provides a better clustering model. Our proposed method can discover hierarchical clustering structure and provides an outstanding performance both in accuracy and execution time.

Invariant Graph Partition Comparison Measures

Symmetric graphs have non-trivial automorphism groups. This article starts with the proof that all partition comparison measures we have found in the literature fail on symmetric graphs, because they are not invariant with regard to the graph automorphisms. By the construction of a pseudometric space of equivalence classes of permutations and with Hausdorff’s and von Neumann’s methods of constructing invariant measures on the space of equivalence classes, we design three different families of invariant measures, and we present two types of invariance proofs. Last, but not least, we provide algorithms for computing invariant partition comparison measures as pseudometrics on the partition space. When combining an invariant partition comparison measure with its classical counterpart, the decomposition of the measure into a structural difference and a difference contributed by the group automorphism is derived.

Group User Profile Modeling Based on Neural Word Embeddings in Social Networks

How to find a user’s interest from similar users a fundamental research problems in socialized recommender systems. Despite significant advances, there exists diversity loss for the majority of recommender systems. With this paper, for expanding the user’s interest, we overcome this challenge by using representative and diverse similar users from followees. First, we model a personal user profile vector via word2vec and term frequency mechanisms. According to user profiles and their follow relationships, we compute content interaction similarity and follow interaction similarity. Second, by combining two kinds of interaction similarity, we calculate the social similarity and discover a diverse group with coverage and dissimilarity. The users in a diverse group can distinguish each other and cover the whole followees, which can model a group user profile (GUP). Then, by tracking the changes of followee set, we heuristically adjust the number of diverse group users and construct an adaptive GUP. Finally, we conduct experiments on Sina Weibo datasets for recommendation, and the experimental results demonstrate that the proposed GUP outperforms conventional approaches for diverse recommendation.

Vertex Labeling and Routing for Farey-Type Symmetrically-Structured Graphs

The generalization of Farey graphs and extended Farey graphs all originate from Farey graphs. They are simultaneously scale-free and small-world. A labeling of the vertices for them are proposed here. All of the shortest paths between any two vertices in these two graphs can be determined only on their labels. The number of shortest paths between any two vertices is the product of two Fibonacci numbers; it is increasing almost linearly with the order or size of the graphs. However, the label-based routing algorithm runs in logarithmic time O(logn). Our efficient routing protocol for Farey-type models should help contribute toward the understanding of several physical dynamic processes.