Cold-Start Link Prediction via Weighted Symmetric Nonnegative Matrix Factorization with Graph Regularization

Link prediction has attracted wide attention among interdisciplinaryresearchers as an important issue in complex network. It aims to predict the missing links in current networks and new links that will appear in future networks.Despite the presence of missing links in the target network of link prediction studies, the network it processes remains macroscopically as a large connectedgraph. However, the complexity of the real world makes the complex networksabstracted from real systems often contain many isolated nodes. This phenomenon leads to existing link prediction methods not to efficiently implement the prediction of missing edges on isolated nodes. Therefore, the cold-start linkprediction is favored as one of the most valuable subproblems of traditional linkprediction. However, due to the loss of many links in the observation network, thetopological information available for completing the link prediction task is extremely scarce. This presents a severe challenge for the study of cold-start link prediction. Therefore, how to mine and fuse more available non-topologicalinformation from observed network becomes the key point to solve the problemof cold-start link prediction. In this paper, we propose a framework for solving thecold-start link prediction problem, a joint-weighted symmetric nonnegative matrixfactorization model fusing graph regularization information, based on low-rankapproximation algorithms in the field of machine learning. First, the nonlinear features in high-dimensional space of node attributes are captured by the designedgraph regularization term. Second, using a weighted matrix, we associate the attribute similarity and first order structure information of nodes and constrain eachother. Finally, a unified framework for implementing cold-start link prediction isconstructed by using a symmetric nonnegative matrix factorization model to integrate the multiple information extracted together. Extensive experimental validationon five real networks with attributes shows that the proposed model has very goodpredictive performance when predicting missing edges of isolated nodes.

Improved Non-negative Matrix Factorization Algorithm for Sparse Graph Regularization

Aiming at the low recognition accuracy of non-negative matrix factorization(NMF)in practical application,an improved spare graph NMF(New-SGNMF)is proposed in this paper.New-SGNMF makes full use of the inherent geometric structure of image data to optimize the basis matrix in two steps.A threshold value s was first set to judge the threshold value of the decomposed base matrix to filter the redundant information in the data.Using L2 norm,sparse constraints were then implemented on the basis matrix,and integrated into the objective function to obtain the objective function of New-SGNMF.In addition,the derivation process of the algorithm and the convergence analysis of the algorithm were given.The experimental results on COIL20,PIE-pose09 and YaleB database show that compared with K-means,PCA,NMF and other algorithms,the proposed algorithm has higher accuracy and normalized mutual information.

Signed total domination in nearly regular graphs

A function f： V（ G）→{1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. An STDF f is minimal if there does not extst a STDF g： V（G）→{-1,1}, f≠g, for which g （ v ）≤f（ v ） for every v∈V（ G ）. The weight of a STDF is the sum of its function values over all vertices. The signed total domination number of G is the minimum weight of a STDF of G, while the upper signed domination number of G is the maximum weight of a minimal STDF of G, In this paper, we present sharp upper bounds on the upper signed total domination number of a nearly regular graph.

Graph Regularized Sparse Coding Method for Highly Undersampled MRI Reconstruction

The imaging speed is a bottleneck for magnetic resonance imaging( MRI) since it appears. To alleviate this difficulty,a novel graph regularized sparse coding method for highly undersampled MRI reconstruction( GSCMRI) was proposed. The graph regularized sparse coding showed the potential in maintaining the geometrical information of the data. In this study, it was incorporated with two-level Bregman iterative procedure that updated the data term in outer-level and learned dictionary in innerlevel. Moreover,the graph regularized sparse coding and simple dictionary updating stages derived by the inner minimization made the proposed algorithm converge in few iterations, meanwhile achieving superior reconstruction performance. Extensive experimental results have demonstrated GSCMRI can consistently recover both real-valued MR images and complex-valued MR data efficiently,and outperform the current state-of-the-art approaches in terms of higher PSNR and lower HFEN values.

ON GRAPHS WITH THREE DISTINCT LAPLACIAN EIGENVALUES

In this paper, an equivalent condition of a graph G with t （2≤ t ≤n） distinct Laplacian eigenvalues is established. By applying this condition to t = 3, if G is regular （necessarily be strongly regular）, an equivalent condition of G being Laplacian integral is given. Also for the case of t = 3, if G is non-regular, it is found that G has diameter 2 and girth at most 5 if G is not a tree. Graph G is characterized in the case of its being triangle-free, bipartite and pentagon-free. In both cases, G is Laplacian integral.

Extracting Sub-Networks from Brain Functional Network Using Graph Regularized Nonnegative Matrix Factorization

Currently,functional connectomes constructed from neuroimaging data have emerged as a powerful tool in identifying brain disorders.If one brain disease just manifests as some cognitive dysfunction,it means that the disease may affect some local connectivity in the brain functional network.That is,there are functional abnormalities in the sub-network.Therefore,it is crucial to accurately identify them in pathological diagnosis.To solve these problems,we proposed a sub-network extraction method based on graph regularization nonnegative matrix factorization(GNMF).The dynamic functional networks of normal subjects and early mild cognitive impairment(eMCI)subjects were vectorized and the functional connection vectors(FCV)were assembled to aggregation matrices.Then GNMF was applied to factorize the aggregation matrix to get the base matrix,in which the column vectors were restored to a common sub-network and a distinctive sub-network,and visualization and statistical analysis were conducted on the two sub-networks,respectively.Experimental results demonstrated that,compared with other matrix factorization methods,the proposed method can more obviously reflect the similarity between the common subnetwork of eMCI subjects and normal subjects,as well as the difference between the distinctive sub-network of eMCI subjects and normal subjects,Therefore,the high-dimensional features in brain functional networks can be best represented locally in the lowdimensional space,which provides a new idea for studying brain functional connectomes.

On λ-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant A such that the equality λd（ui） = ∑（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,…, ｜V（G）｜, where d（vi） denotes the degree of vertex vi. In this paper, some harmonic properties of the complement and line graph are given, and some algebraic properties for the λ-Hgraphs are obtained.

Search algorithm on strongly regular graphs based on scattering quantum walks

Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm＇s performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O（√N） time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.

REGULAR k-COVERED GRAPHS

A graph G is k-covered if each edge of G belongs to a k-factor of G. We determine some valuee of k for which every r-regular graph with edge-connectivity λ is k-covered.

Laplacian Energies of Regular Graph Transformations

Let LE(G) denote the Laplacian energy of a graph G. In this paper the xyz-transformations G^(xyz) of an r-regular graph G for x,y,z∈{0,1, +,-} are considered. The explicit formulas of LE(G^(xyz)) are presented in terms of r,the number of vertices of G for any positive integer r and x,y,z∈{ 0,1},and also for r = 2 and all x,y,z∈{0,1,+,-}. Some Laplacian equienergetic pairs of G^(xyz) for r = 2 and x,y,z∈{0,1, +,-} are obtained. This also provides several ways to construct infinitely many pairs of Laplacian equienergetic graphs.

Generalized Krein Parameters of a Strongly Regular Graph

We consider the real three-dimensional Euclidean Jordan algebra associated to a strongly regular graph. Then, the Krein parameters of a strongly regular graph are generalized and some generalized Krein admissibility conditions are deduced. Furthermore, we establish some relations between the classical Krein parameters and the generalized Krein parameters.

ON THE ASCENDING SUBGRAPH DECOMPOSITIONS OF REGULAR GRAPHS

The definition of the ascending subgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.

A family of generalized strongly regular graphs of grade 2

A generalized strongly regular graphof grade p,as anew generalization of strongly regular graphs,is a regular graph such that the number of common neighbours of both any two adjacent vertices and any two non-adjacent vertices takes on p distinct values.For any vertex u of a generalized strongly regular graph of grade 2 with parameters(n,k;a_(1),a_(2);c_(1),c_(2)),if the number of the vertices that are adjacent to u and share ai(i=1,2)common neighbours with u,or are non-adjacent to u and share c,(i=1,2)common neighbours with is independent of the choice of the vertex u,then the generalized strongly regular graph of grade 2 is free.In this paper,we investigate the generalized strongly regular graph of grade 2 with parameters(n,k;k-1,a_(2);k-1,c_(2))and provide the sufficient and necessary conditions for the existence of a family of free generalized strongly regular graphs of grade 2.

Regular and Maximal Graphs with Prescribed Tripartite Graph as a Star Complement

Let G be a graph of order n andμbe an adjacency eigenvalue of G with multiplicity k≥1.A star complement H forμin G is an induced subgraph of G of order n-k with no eigenvalueμ,and the subset X=V(G-H)is called a star set forμin G.The star complement provides a strong link between graph structure and linear algebra.In this paper,the authors characterize the regular graphs with K2,2,s(s≥2)as a star complement for all possible eigenvalues,the maximal graphs with K2,2,s as a star complement for the eigenvalueμ=1,and propose some questions for further research.

The Adjacency Codes of the First Yellow Graphs

The authors study the binary codes spanned by the adjacency matrices of the strongly regular graphs(SRGs)on at most two hundred vertices whose existence is unknown.The authors show that in length less than one hundred they cannot be cyclic,except for the exceptions of the SRGs of parameters(85,42,20,21)and(96,60,38,36).In particular,the adjacency code of a(85,42,20,21)is the zero-sum code.In the range[100,200]the authors find 29 SRGs that could possibly have a cyclic adjacency code.

The Non-Inclusive Diagnosability of Regular Graphs

Fault diagnosis is an important area of study with regard to the design and maintenance of multiprocessor systems.A new measure for fault diagnosis of systems,namely,non-inclusive diagnosability(denoted by MM^(*)),was proposed by Ding et al.In this paper,we establish the non-inclusive diagnosability of a class of regular graphs under the PMC model and the MM^(*)model.As applications,the non-inclusive diagnosabilities of hypercubes,hierarchical hypercubes,folded hypercubes,star graphs,bubble-sort graphs,pancake graphs and dual cubes are determined under the PMC model and the[Math Processing Error]model.

Clique-Transversal Sets in 4-Regular Claw-Free Graphs

A clique-transversal set D of a graph C is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by To（G）, is the minimum cardinality of a clique- transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.

Smallest Close to Regular Bipartite Graphs without an Almost Perfect Matching

A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.

Weak Internal Partition of Regular Graphs

An(s,t)-partition of a graph G=(V,E)is a partition of V=V 1∪V 2 suchthatδ(G[V_(1)])≥s andδ(G[V_(2)])≥t.Ithasbeenconjecturedthat,forsufficiently large n,every d-regular graph of order n has a(d/2,d/2)-partition(called an internal partition).Inthispaper,weprovethateveryd-regulargraphofordern hasa(d/2,d/2)partition(called a weak internal partition)for d≤9 and sufficiently large n.

k-Factors in Regular Graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.