Subgraphs of Interest Social Networks for Diffusion Dynamics Prediction

Finding the building blocks of real-world networks contributes to the understanding of their formation process and related dynamical processes, which is related to prediction and control tasks. We explore different types of social networks, demonstrating high structural variability, and aim to extract and see their minimal building blocks, which are able to reproduce supergraph structural and dynamical properties, so as to be appropriate for diffusion prediction for the whole graph on the base of its small subgraph. For this purpose, we determine topological and functional formal criteria and explore sampling techniques. Using the method that provides the best correspondence to both criteria, we explore the building blocks of interest networks. The best sampling method allows one to extract subgraphs of optimal 30 nodes, which reproduce path lengths, clustering, and degree particularities of an initial graph. The extracted subgraphs are different for the considered interest networks, and provide interesting material for the global dynamics exploration on the mesoscale base.     

Hereditary Efficiently Dominatable Graphs

An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. We introduce graphs that are hereditary efficiently dominatable in that sense that every induced subgraph of the graph contains an efficient dominating set. We prove a decomposition theorem for (bull, fork, C₄)‐free graphs, based on which we characterize, in terms of forbidden induced subgraphs, the class of hereditary efficiently dominatable graphs. We also give a decomposition theorem for hereditary efficiently dominatable graphs and examine some algorithmic aspects of such graphs. In particular, we give a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs by reducing the problem to the maximum weight independent set problem in claw‐free graphs.     

HC-HDSD: A method of hypergraph construction and high-density subgraph detection for inferring high-order epistatic interactions

Detecting epistatic interactions, or nonlinear interactive effects of Single Nucleotide Polymorphisms (SNPs), has gained increasing attention in explaining the “missing heritability” of complex diseases. Though much work has been done in mapping SNPs underlying diseases, most of them constrain to 2-order epistatic interactions. In this paper, a method of hypergraph construction and high-density subgraph detection, named HC-HDSD, is proposed for detecting high-order epistatic interactions. The hypergraph is constructed by low-order epistatic interactions that identified using the normalized co-information measure and the exhaustive search. The hypergraph consists of two types of vertices: real ones representing main effects of SNPs and virtual ones denoting interactive effects of epistatic interactions. Then, both maximal clique centrality algorithm and near-clique mining algorithm are employed to detect high-density subgraphs from the constructed hypergraph. These high-density subgraphs are inferred as high-order epistatic interactions in the HC-HDSD. Experiments are performed on several simulation data sets, results of which show that HC-HDSD is promising in inferring high-order epistatic interactions while substantially reducing the computation cost. In addition, the application of HC-HDSD on a real Age-related Macular Degeneration (AMD) data set provides several new clues for the exploration of causative factors of AMD.     

All good (bad) words consisting of 5 blocks

Generalized Fibonacci cube Q_d(f), introduced by Ilic, Klavzar and Rho, is the graph obtained from the hypercube Q_d by removing all vertices that contain f as factor. A word f is good if Q_d(f) is an isometric subgraph of Q_d for all d ≥ 1, and bad otherwise. A non-extendable sequence of contiguous equal digits in a word μ is called a block of μ. Ilic, Klavzar and Rho shown that all the words consisting of one block are good, and all the words consisting of three blocks are bad. So a natural problem is to study the words consisting of other odd number of blocks. In the present paper,a necessary condition for a word consisting of odd number of blocks being good is given, and all the good(bad) words consisting of 5 blocks is determined.     

有机化合物热力学性质的预测(Ⅲ)——人工神经网络法预测烷烃的生成焓

采用分子子图编码方法将烷烃的分子子图码作为人工神经网络(ANN)的输入参数 ,对烷烃的生成焓进行预测 ,取得了满意的结果 ,其拟合方程的回归系数达到 0 .9845     

STABILITY NUMBER IN SUBCLASSES OF P_5~-FREE GRAPHS

§1　IntroductionLet Pn,Cn,and Kn be the path,the cycle,and the complete graph of order n,respectively.The complete bipartite graph with cardinalities ofparts m and n is denoted byKm,n.Disjoint union of n copies of a graph G is denoted by n G;Gis the complement of agraph G.A setof pairwise non-adjacent vertices in a graph is called stable.A maximum stableset of a graph G has the largest cardinalityα( G) among all stable sets of G;α( G) is calledthe stability number of G.Let Z be a s…     

Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:

• (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:
  • (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/3+c^1/(3r+3))n² edges.
  Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions:
  • (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/4+c^1/(8r+8))n² edges.
  © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009     

Maximum bipartite subgraphs of cubic triangle-free planar graphs

Thomassen recently proved, using the Tutte cycle technique, that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least edges, improving the previously known lower bound . We extend Thomassen’s technique and further improve this lower bound to .