Graphs Isomorphic to Their Maximum Matching Graphs

The maximum matching graph M（G） of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M（G） if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle.

Overlap maximum matching ratio （OMMR）： a new measure to evaluate overlaps of essential modules

Protein complexes are the basic units of macro-molecular organizations and help us to understand the cell's mechanism.The development of the yeast two-hybrid,tandem affinity purification,and mass spectrometry high-throughput proteomic techniques supplies a large amount of protein-protein interaction data,which make it possible to predict overlapping complexes through computational methods.Research shows that overlapping complexes can contribute to identifying essential proteins,which are necessary for the organism to survive and reproduce,and for life's activities.Scholars pay more attention to the evaluation of protein complexes.However,few of them focus on predicted overlaps.In this paper,an evaluation criterion called overlap maximum matching ratio(OMMR) is proposed to analyze the similarity between the identified overlaps and the benchmark overlap modules.Comparison of essential proteins and gene ontology(GO) analysis are also used to assess the quality of overlaps.We perform a comprehensive comparison of serveral overlapping complexes prediction approaches,using three yeast protein-protein interaction(PPI) networks.We focus on the analysis of overlaps identified by these algorithms.Experimental results indicate the important of overlaps and reveal the relationship between overlaps and identification of essential proteins.

THE CONNECTIVITY OF MAXIMUM MATCHING GRAPHS

The maximum matching graph of a graph has a vertex for each maximummatching and an edge for each pair of maximum matchings which differ by exactly oneedge. In this paper, we prove that the connectivity of maximum matching graph of abipartite graph is equal to its minimum degree.

Distance Between Two Vertices of Maximum Matching Graphs

The maximum matching graph of a graph has a vertex for each maximum matching and an edge for each pair of maximum matchings which differ by exactly one edge. In this paper, we obtain a lower bound of distance between two vertices of maximum matching graph, and give a necessary and sufficient condition that the bound can be reached.

2-Connected Factor-critical Graphs G with Exactly ｜E(G)｜ ＋ 1 Maximum Matchings

A connected graph G is said to be a factor-critical graph if G - v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly ｜E（G）｜＋ 1 maximum matchings is characterized.

Time Complexity Analysis of an Evolutionary Algorithm for Finding Nearly Maximum Cardinality Matching

Most of works on the time complexity analysis of evolutionary algorithms havealways focused on some artificial binary problems. The time complexity of the algorithms forcombinatorial optimisation has not been well understood. This paper considers the time complexity ofan evolutionary algorithm for a classical combinatorial optimisation problem, to find the maximumcardinality matching in a graph. It is shown that the evolutionary algorithm can produce a matchingwith nearly maximum cardinality in average polynomial time.

Matching Algorithms of Minimum Input Selection for Structural Controllability Based on Semi-Tensor Product of Matrices

In 2011,Liu,et al.investigated the structural controllability of directed networks.They proved that the minimum number of input signals,driver nodes,can be determined by seeking a maximum matching in the directed network.Thus,the algorithm for seeking a maximum matching is the key to solving the structural controllability problem of directed networks.In this study,the authors provide algebraic expressions for matchings and maximum matchings proposed by Liu,et al.(2011)via a new matrix product called semi-tensor product,based on which the corresponding algorithms are established to seek matchings and maximum matchings in digraphs,which make determining the number of driver nodes tractable in computer.In addition,according to the proposed algorithm,the authors also construct an algorithm to distinguish critical arcs,redundant arcs and ordinary arcs of the directed network,which plays an important role in studying the robust control problem.An example of a small network from Liu’s paper is used for algorithm verification.

Matching user identities across social networks with limited profile data

Privacy preservation is a primary concern in social networks which employ a variety of privacy preservations mechanisms to preserve and protect sensitive user information including age,location,education,interests,and others.The task of matching user identities across different social networks is considered a challenging task.In this work,we propose an algorithm to reveal user identities as a set of linked accounts from different social networks using limited user profile data,i.e,user-name and friendship.Thus,we propose a framework,ExpandUIL,that includes three standalone al-gorithms based on(i)the percolation graph matching in Ex-pand FullName algorithm,(i)a supervised machine learning algorithm that works with the graph embedding,and(ii)a combination of the two,ExpandUserLinkage algorithm.The proposed framework as a set of algorithms is significant as,(i)it is based on the network topology and requires only name feature of the nodes,(i)it requires a considerably low initial seed,as low as one initial seed suffices,(ii)it is iterative and scalable with applicability to online incoming stream graphs,and(iv)it has an experimental proof of stability over a real ground-truth dataset.Experiments on real datasets,Instagram and VK social networks,show upto 75%recall for linked ac-counts with 96%accuracy using only one given seed pair.