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.

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.