Propagation models are essential for modeling and simulating dynamic processes such as epidemics and information diffusion. However, existing tools struggle to scale to large-scale graphs that emerge across social networks, epidemic networks and so on, due to limited algorithmic efficiency, weak scalability, and high communication overhead. We present FS_GPlib, a unified library that enables efficient, high-fidelity propagation modeling on Web-scale graphs. FS_GPlib introduces a dual-acceleration framework: it combines micro-level synchronous message-passing updates with macro-level batched Monte Carlo simulation, leveraging high-dimensional tensor operations for parallel execution. To further enhance scalability, it supports distributed simulation via a novel target-node-based graph partitioning strategy that minimizes communication overhead while maintaining load balance. Theoretically, we show that under ideal assumptions, the runtime of simulations converges approximately to a constant. Extensive experiments demonstrate up to 35,000× speedup over standard libraries such as NDlib and execution of a full Monte Carlo simulation on a Web-scale (billion-edge) graph in 11 seconds while maintaining high simulation fidelity. FS_GPlib supports 29 propagation models—including epidemic and opinion dynamics and dynamic network models—and offers a lightweight Python API compatible with mainstream data science ecosystems. By addressing the unique challenges of modeling diffusion and cascades on the Web, FS_GPlib provides a scalable, extensible, and theoretically grounded solution for large-scale propagation analysis in epidemiology, social media analysis, and online network dynamics. Code available at: https://github.com/Allen-Ciel/FS_GPlib.

Inferring latent interaction structures from observational time series is a fundamental yet challenging problem in dynamical systems. Existing deep learning methods employ unidirectional information aggregation via incoming edges, failing to identify the mutual dependencies prevalent in real dynamics as well as the feedback effects induced by sampling intervals, which leads to inferential bias. To address this, we propose the D ual- A ttention R elational I nference (DARI), a framework designed to learn latent interaction structures from dynamical observations. DARI employs a coupled bidirectional attention mechanism to model forward and feedback dynamics, effectively decoupling information flow from the underlying interaction structure. Extensive synthetic experiments demonstrate competitive structural recovery performance across diverse graph topologies, including undirected, directed, and weighted graphs. Experiments on COVID-19 data further show that the inferred transmission structures are consistent with real-world population mobility patterns. In addition, the elimination of costly edge-wise computations in DARI leads to substantial gains in both runtime and memory efficiency. Code is available at https://anonymous.4open.science/r/DARI-778C .

Information cocooning—amplified by algorithmic filtering—poses complex challenges for emotional dynamics in online social networks. This study explores how algorithmically reinforced information cocooning shapes information diffusion and group emotional dynamics in online social networks. We propose a viewpoint-based network evolution model that simulates structural transformations driven by user preferences. To model the hidden influence of personalized comment recommendations, we introduce the hidden comment area cocoon (H-CAC)—a novel higher-order structure that captures cocooning at the comment level. This structure is integrated into an emotion spreading model, enabling the quantification of how cocooning affects collective sentiment. By defining recommendation accuracy as a tunable parameter, we systematically evaluate its impact on emotional volatility and polarization. Extensive simulations, validated with real-world data, reveal that while cocooning reduces content diversity, it can significantly enhance emotional resilience within groups. Our findings offer a new computational lens on the dual role of cocooning and provide actionable insights for designing emotionally stable, algorithmically governed social platforms.

In recent years, phishing scams have become one of the most rampant criminal activities on Ethereum, causing significant financial losses to investors and disruptions to the Ethereum ecosystem. Existing phishing scam detection methods typically model Ethereum transaction records as graphs, extracting features from paired nodes based on the topological relationships. However, these methods mostly focus on low-order relational aspects, neglecting higher-order structural information in the network. In this paper, we propose a new method — Ethereum Phishing Scam Detection by Higher-Order Topology (EPSD-HOT), which improves phishing scam detection performance by mining higher-order topological features from the network. We conduct experiments on a public dataset and a crawled real-world dataset, extracting ten subgraphs with distinct network characteristics. The experimental results show that the average AUC-ROC for the ten subgraphs is 0.9970, with improvements ranging from 0.0181 to 0.1658 compared to baseline methods. This indicates that our approach is highly robust and can effectively detect phishing scams across different subgraphs while overcoming the issue of class imbalance. By incorporating higher-order structural information into node features, this work offers new insights for enhancing phishing scam detection in Ethereum.

Synchronization is essential for the stability and coordinated operation of complex networked systems. Pinning control, which selectively controls a subset of nodes, provides a scalable solution to enhance network synchronizability. However, existing strategies face key limitations. Heuristic centrality-based methods lack a direct connection to synchronization dynamics, while spectral approaches, though effective, are computationally intensive. To address these challenges, we propose a perturbation-based optimized (PBO) strategy that dynamically evaluates each node’s spectral impact on the Laplacian matrix, achieving improved synchronizability with significantly reduced computational costs (with complexity$O(kM)$). Extensive experiments demonstrate that the proposed method outperforms traditional strategies in synchronizability, convergence rate, and pinning robustness to node failures. Notably, in all the empirical networks tested and some generated networks, PBO significantly outperforms the brute-force greedy (BFG) strategy, demonstrating its ability to avoid local optima and adapt to complex connectivity patterns. Our study establishes the theoretical relationship between network synchronizability and convergence rate, offering new insights into efficient synchronization strategies for large-scale complex networks.

Heterogeneous Graph Neural Networks (HGNNs) are extensively applied in modeling web-based applications that involve heterogeneous graph structures. Explanation models for HGNNs aim to address their ''black box'' nature. Enhancing the interpretability of HGNNs leads to a better understanding and can potentially improve predictive performance. However, existing post-hoc HGNN explanation methods cannot impact the HGNN's predictions. Self-explainable homogeneous models also perform poorly on heterogeneous graphs. To address these challenges, we present a Self-Explainable Heterogeneous Graph Neural Network (SEHG), a novel architecture that integrates explanation generation into the learning process of HGNN through two alternative stages. The first stage focuses on producing high-quality explanations while providing predictions alongside. The second stage enhances prediction accuracy by a contrastive learning strategy. Unlike the current methods that rely on manually defined metapaths for structural explanations, SEHG generates important structure and feature explanations by learnable heterogeneous masks. To ensure high-quality and sparsity explanation, these masks are regulated by a uniquely designed range-based penalty during training. Moreover, we introduce HetBA, a collection of synthetic heterogeneous datasets designed to quantify and visualize explanations or heterogeneous graphs. Extensive experiments demonstrate the effectiveness of SEHG, which surpasses strong baselines in real-world node classification tasks by notable margins of up to 3.91%. SEHG also achieves state-of-the-art performance on synthetic datasets with improvement of up to 9.44%, and records the highest fidelity scores in explanation tasks, improving by up to 46.57%. To our knowledge, SEHG is a pioneering self-explainable HGNN framework that achieves state-of-the-art performance on both heterogeneous graph explanation and prediction tasks.

Exploring the internal mechanism of information spreading is critical for understanding and controlling the process. Traditional spreading models often assume individuals play the same role in the spreading process. In reality, however, individuals’ diverse characteristics contribute differently to the spreading performance, leading to a heterogeneous infection rate across the system. To investigate network spreading dynamics under heterogeneous infection rates, we integrate two individual-level features—influence (i.e., the ability to influence neighbors) and susceptibility (i.e., the extent to be influenced by neighbors)—into the independent cascade model. Our findings reveal significant differences in spreading performance under heterogeneous and constant infection rates, with traditional structural centrality metrics proving more effective in the latter scenario. Additionally, we take the constant and heterogeneous infection rates into a state-of-the-art maximization algorithm, the well-known TIM algorithm, and find the seeds selected by heterogeneous infection rates are more dispersed compared to those under constant rates. Lastly, we find that both individuals’ influence and susceptibility are vital to the spreading performance. Strikingly, susceptible individuals are particularly important to spreading when information is disseminated by social celebrities. By integrating influence and susceptibility into the spreading model, we gain a more profound understanding of the underlying mechanisms driving information spreading.

Despite the recent successes of vanilla Graph Neural Networks (GNNs) on various tasks, their foundation on pairwise networks inherently limits their capacity to discern latent higher-order interactions in complex systems. To bridge this capability gap, we propose a novel approach exploiting the rich mathematical theory of simplicial complexes (SCs) - a robust tool for modeling higher-order interactions. Current SC-based GNNs are burdened by high complexity and rigidity, and quantifying higher-order interaction strengths remains challenging. Innovatively, we present a higher-order Flower-Petals (FP) model, incorporating FP Laplacians into SCs. Further, we introduce a Higher-order Graph Convolutional Network (HiGCN) grounded in FP Laplacians, capable of discerning intrinsic features across varying topological scales. By employing learnable graph filters, a parameter group within each FP Laplacian domain, we can identify diverse patterns where the filters' weights serve as a quantifiable measure of higher-order interaction strengths. The theoretical underpinnings of HiGCN's advanced expressiveness are rigorously demonstrated. Additionally, our empirical investigations reveal that the proposed model accomplishes state-of-the-art performance on a range of graph tasks and provides a scalable and flexible solution to explore higher-order interactions in graphs. Codes and datasets are available at https://github.com/Yiminghh/HiGCN.

Finding an optimal subset of nodes or links to disintegrate harmful networks is a fundamental problem in network science, with potential applications to anti-terrorism, epidemic control, and many other fields of study. The challenge of the network disintegration problem is to balance the effectiveness and efficiency of strategies. In this article, we propose a cost-effective targeted enumeration (TE) method for network disintegration. The proposed approach includes two stages: 1) searching for candidate objects and 2) identifying an optimal solution. In the first stage, we use rank aggregation to generate a comprehensive ranking of node importance, upon which we identify a small-scale candidate set of nodes to remove. In the second stage, we use an enumeration method to find an optimal combination among the candidate nodes. Extensive experimental results on synthetic and real-world networks demonstrate that the proposed method achieves a satisfying tradeoff between effectiveness and efficiency. Our adaptable TE approach can effectively address a range of combinatorial optimization challenges with significant potential applications, including personnel recruitment, portfolio management, and pharmaceutical development.

Traffic signal control (TSC) is still one of the most significant and challenging research problems in the transportation field. Reinforcement learning (RL) has achieved great success in TSC but suffers from critically high learning costs in practical applications due to the excessive trial-and-error learning process. Offline RL is a promising method to reduce learning costs whereas the data distribution shift issue is still up in the air. To this end, in this paper, we formulate TSC as a sequence modeling problem with a sequence of Markov decision process described by states, actions, and rewards from the traffic environment. A novel framework, namely TransformerLight, is introduced, which does not aim to fit into value functions by averaging all possible returns, but produces the best possible actions using a gated Transformer. Additionally, the learning process of TransformerLight is much more stable by replacing the residual connections with gated transformer blocks due to a dynamic system perspective. Through numerical experiments on offline datasets, we demonstrate that the TransformerLight model: (1) can build a high-performance adaptive TSC model without dynamic programming; (2) achieves a new state-of-the-art compared to most published offline RL methods so far; and (3) shows a more stable learning process than offline RL and recent Transformer-based methods. The relevant dataset and code are available at Github.

Abstract. An edge-colored graph [Formula: see text] is called rainbow if every edge of [Formula: see text] receives a different color. Given any host multigraph [Formula: see text], the anti-Ramsey number of [Formula: see text] edge-disjoint rainbow spanning trees in [Formula: see text], denoted by [Formula: see text], is defined as the maximum number of colors in an edge-coloring of [Formula: see text] containing no [Formula: see text] edge-disjoint rainbow spanning trees. For any vertex partition [Formula: see text], let [Formula: see text] be the set of noncrossing edges in [Formula: see text] with respect to [Formula: see text]. In this paper, we determine [Formula: see text] for all host multigraphs [Formula: see text]: [Formula: see text] if there exists a partition [Formula: see text] with [Formula: see text]; and [Formula: see text] otherwise. As a corollary, we determine [Formula: see text] for all values of [Formula: see text], improving a result of Jia, Lu, and Zhang.

Many studies confirmed that a proper traffic state representation is more important than complex algorithms for the classical traffic signal control (TSC) problem. In this paper, we (1) present a novel, flexible and efficient method, namely advanced max pressure (Advanced-MP), taking both running and queuing vehicles into consideration to decide whether to change current signal phase; (2) inventively design the traffic movement representation with the efficient pressure and effective running vehicles from Advanced-MP, namely advanced traffic state (ATS); and (3) develop a reinforcement learning (RL) based algorithm template, called Advanced-XLight, by combining ATS with the latest RL approaches, and generate two RL algorithms, namely "Advanced-MPLight" and "Advanced-CoLight" from Advanced-XLight. Comprehensive experiments on multiple real-world datasets show that: (1) the Advanced-MP outperforms baseline methods, and it is also efficient and reliable for deployment; and (2) Advanced-MPLight and Advanced-CoLight can achieve the state-of-the-art.

Studying networked systems in a variety of domains, including biology, social science, and Internet of Things, has recently received a surge of attention. For a networked system, there are usually multiple types of interactions between its components, and such interaction-type information is crucial since it always associated with important features. However, some interaction types that actually exist in the network may not be observed in the metadata collected in practice. This article proposes an approach aiming to detect previously undiscovered interaction types (PUITs) in networked systems. The first step in our proposed PUIT detection approach is to answer the following fundamental question: is it possible to effectively detect PUITs without utilizing metadata other than the existing incomplete interaction-type information and the connection information of the system? Here, we first propose a temporal network model which can be used to mimic any real network and then discover that some special networks which fit the model shall a common topological property. Supported by this discovery, we finally develop a PUIT detection method for networks which fit the proposed model. Both analytical and numerical results show this detection method is more effective than the baseline method, demonstrating that effectively detecting PUITs in networks is achievable. More studies on PUIT detection are of significance and in great need since this approach should be as essential as the previously undiscovered node-type detection which has gained great success in the field of biology.

Large-scale risk events in the venture capital (VC) market can easily lead to systemic risk in the financial market. This paper collects the comprehensive dataset of Chinese VC market from 1999 to 2020, and constructs the multi-layer networks of VC market. After that, a risk contagion model of venture capital market is designed considering both the capital loss transmission and social relations effect (investor herd behavior). By simulating various situations with different risk origins and scales, the speed of risk contagion and the total impacts on the overall stability of the market (network) are compared. We find that the herd behavior of the market will generally aggravate the consequences of risk contagion. Compared with unicorns, the failure of a leading VC firm can cause a wider range of risk contagion. The contagion consequences caused by the failure of random financing companies are more serious than those caused by random VC firms. Moreover, we identify that telecommunications services and information technology are high-risk industries in VC market. Based on the empirical results, this article provides policy implications for the market regulatory sectors to prevent VC market risks.

Venture capital market is one of the most important financial markets, which plays an important role in promoting industrial innovation and economic development. In this study, the complete data set of all venture capital events occurred in China from 2009 to 2020 was used to construct two kinds of complex networks, whose topological property and dynamic evolution trend of the network are studied. Specifically, we construct the co-investment network among investor, as well as the binary complex network of investor-entrepreneur, and propose the evaluation method of the importance and performance of venture capital institutions. Based on the proposed method, we identify some leading venture capital institutions with high performance and importance. Furthermore, this paper enlightens venture capital practitioners by discovering the investment behavior and preference of these leading institutions.

An edge-colored graph $G$ is called rainbow if every edge of $G$ receives a different color. The anti-Ramsey number of $t$ edge-disjoint rainbow spanning trees, denoted by $r(n,t)$, is defined as the maximum number of colors in an edge-coloring of $K_n$ containing no $t$ edge-disjoint rainbow spanning trees. Jahanbekam and West [ J. Graph Theory, 82 (2016), pp. 75--89] conjectured that for any fixed $t$, $r(n,t)=(\begin{smallmatrix}{n-2}\\{2}\end{smallmatrix})+t$ whenever $n\geq 2t+2 \geq 6$. In this paper, we prove this conjecture. We also determine $r(n,t)$ when $n = 2t+1$. Together with previous results, this gives the anti-Ramsey number of $t$ edge-disjoint rainbow spanning trees for all values of $n$ and $t$.

Accurate prioritization of potential disease genes is a fundamental challenge in biomedical research. Various algorithms have been developed to solve such problems. Inductive Matrix Completion (IMC) is one of the most reliable models for its well-established framework and its superior performance in predicting gene-disease associations. However, the IMC method does not hierarchically extract deep features, which might limit the quality of recovery. In this case, the architecture of deep learning, which obtains high-level representations and handles noises and outliers presented in large-scale biological datasets, is introduced into the side information of genes in our Deep Collaborative Filtering (DCF) model. Further, for lack of negative examples, we also exploit Positive-Unlabeled (PU) learning formulation to low-rank matrix completion. Our approach achieves substantially improved performance over other state-of-the-art methods on diseases from the Online Mendelian Inheritance in Man (OMIM) database. Our approach is 10 percent more efficient than standard IMC in detecting a true association, and significantly outperforms other alternatives in terms of the precision-recall metric at the top-k predictions. Moreover, we also validate the disease with no previously known gene associations and newly reported OMIM associations. The experimental results show that DCF is still satisfactory for ranking novel disease phenotypes as well as mining unexplored relationships. The source code and the data are available at https://github.com/xzenglab/DCF.

Motivation: The identification of disease-related microRNAs (miRNAs) is an essential but challenging task in bioinformatics research. Similarity-based link prediction methods are often used to predict potential associations between miRNAs and diseases. In these methods, all unobserved associations are ranked by their similarity scores. Higher score indicates higher probability of existence. However, most previous studies mainly focus on designing advanced methods to improve the prediction accuracy while neglect to investigate the link predictability of the networks that present the miRNAs and diseases associations. In this work, we construct a bilayer network by integrating the miRNA-disease network, the miRNA similarity network and the disease similarity network. We use structural consistency as an indicator to estimate the link predictability of the related networks. On the basis of the indicator, a derivative algorithm, called structural perturbation method (SPM), is applied to predict potential associations between miRNAs and diseases. Results: The link predictability of bilayer network is higher than that of miRNA-disease network, indicating that the prediction of potential miRNAs-diseases associations on bilayer network can achieve higher accuracy than based merely on the miRNA-disease network. A comparison between the SPM and other algorithms reveals the reliable performance of SPM which performed well in a 5-fold cross-validation. We test fifteen networks. The AUC values of SPM are higher than some well-known methods, indicating that SPM could serve as a useful computational method for improving the identification accuracy of miRNA‒disease associations. Moreover, in a case study on breast neoplasm, 80% of the top-20 predicted miRNAs have been manually confirmed by previous experimental studies. Availability and implementation: https://github.com/lecea/SPM-code.git. Supplementary information: Supplementary data are available at Bioinformatics online.

For any $r\geq 2$ and $k\geq 3$, the $r$-color size-Ramsey number $\hat R(\mathcal{G},r)$ of a $k$-uniform hypergraph $\mathcal{G}$ is the smallest integer $m$ such that there exists a $k$-uniform hypergraph $\mathcal{H}$ on $m$ edges such that any coloring of the edges of $\mathcal{H}$ with $r$ colors yields a monochromatic copy of $\mathcal{G}$. Let $\mathcal{P}_{n,k-1}^{(k)}$ denote the $k$-uniform tight path on $n$ vertices. Dudek et al. [ J. Graph Theory, 86 (2017), pp. 104--121] showed that the size-Ramsey number of tight paths $\hat R(\mathcal{P}_{n,k-1}^{(k)}, 2) = O(n^{k-1-\alpha} (\log n)^{1+\alpha})$ where $\alpha = (k-2)/(\binom{k-1}{2}+1)$. In this paper, we improve their bound by showing that $\hat R(\mathcal{P}_{n,k-1}^{(k)}, r) = O(r^k (n\log n)^{k/2})$ for all $k\geq 3$ and $r\geq 2$.

Recommender systems, inferring users' preferences from their historical activities and personal profiles, have been an enormous success in the last several years. Most of the existing works are based on the similarities of users, objects or both that derived from their purchases records in the online shopping platforms. Such approaches, however, are facing bottlenecks when the known information is limited. The extreme case is how to recommend products to new users, namely the so-called cold-start problem. The rise of the online social networks gives us a chance to break the glass ceiling. Birds of a feather flock together. Close friends may have similar hidden pattern of selecting products and the advices from friends are more trustworthy. In this paper, we integrate the individual's social relationships into recommender systems and propose a new method, called Social Mass Diffusion (SMD), based on a mass diffusion process in the combined network of users' social network and user-item bipartite network. The results show that the SMD algorithm can achieve higher recommendation accuracy than the Mass Diffusion (MD) purely on the bipartite network. Especially, the improvement is striking for small degree users. Moreover, SMD provides a good solution to the cold-start problem. The recommendation accuracy for new users significantly higher than that of the conventional popularity-based algorithm. These results may shed some light on the new designs of better personalized recommender systems and information services.

In this paper, we empirically analyze the spatial distribution of Chinese cities using a method based on triangle transition. This method uses a regular triangle mapping from the observed cities and its three neighboring cities to analyze their distribution of mapping positions. We find that obvious center-gathering tendency for the relationship between cities and its nearest three cities, indicating the spatial competition between cities. Moreover, we observed the competitive trends between neighboring cities with similar economic volume, and the remarkable cooperative tendency between neighboring cities with large difference on economy. The threshold of the ratio of the two cities' economic volume on the transition from competition to cooperation is about 1.2. These findings are helpful in the understanding of the cities economic relationship, especially in the study of competition and cooperation between cities.

Let $\Delta(G)$ be the maximum degree of a graph G. Brooks' theorem states that the only connected graphs with chromatic number $\chi(G)=\Delta(G)+1$ are complete graphs and odd cycles. We prove a fractional analogue of Brooks' theorem in this paper. Namely, we classify all connected graphs G such that the fractional chromatic number $\chi_f(G)$ is at least $\Delta(G)$. These graphs are complete graphs, odd cycles, $C^2_8$, $C_5\boxtimes K_2$, and graphs whose clique number $\omega(G)$ equals the maximum degree $\Delta(G)$. Among the two sporadic graphs, the graph $C^2_8$ is the square graph of cycle $C_8$, while the other graph $C_5\boxtimes K_2$ is the strong product of $C_5$ and $K_2$. In fact, we prove a stronger result: If a connected graph G with $\Delta(G)\geq 4$ is not one of the graphs listed above, then we have $\chi_f(G)\leq \Delta(G)- \frac{2}{67}$.

The routing number $rt(G)$ of a connected graph G is the minimum integer r so that every permutation of vertices can be routed in r steps by swapping the ends of disjoint edges. In this paper, we study the routing numbers of cycles, complete bipartite graphs, and hypercubes. We prove that $rt(C_n)=n-1$ (for $n\geq3$) and for $s\geq t$, $rt(K_{s,t})=\lfloor\frac{3s}{2t}\rfloor+O(1)$. We also prove $n+1\leq rt(Q_n)\leq2n-2$ for $n\geq3$. The lower bound $rt(Q_n)\geq n+1$ was previously conjectured by Alon, Chung, and Graham [SIAM J. Discrete Math., 7 (1994), pp. 513–530]. A variation, called fractional routing number, is also considered in this paper.

Sorting permutations by transpositions is an important and difficult problem in genome rearrangements. The transposition diameter $TD(n)$ is the maximum transposition distance among all pairs of permutations in $S_n$. It was previously conjectured [H. Eriksson et al., Discrete Math., 241 (2001), pp. 289–300] that $TD(n)\leq\lceil\frac{n+1}{2}\rceil$. This conjecture was disproved by Elias and Hartman [IEEE/ACM Trans. Comput. Biol. Bioinform., 3 (2006), pp. 369–379] by showing $TD(n)\geq\lfloor\frac{n+1}{2}\rfloor+1$. In this paper we improved the lower bound to $TD(n)\geq\frac{17}{33}n+\frac{1}{33}$ via computation.

We first answer a question of de Caen [Extremal Problems for Finite Sets, János Bolyai Math. Soc., Budapest, 1994, pp. 187–197]: given $r\geq3$, if G is an r-uniform hypergraph on n vertices such that every $r+1$ vertices span 1 or $r+1$ edges, then $G=K^r_n$ or $K^r_{n-1}$, assuming that $n>(p-1)r$, where p is the smallest prime factor of $r-1$. We then show that the Turán density $\pi(K^r_{r+1})\leq1-1/r-(1-1/r^{p-1})(r-1)^2/(2r^p({r+p\choose p-1}+{r+1\choose 2}))$, for all even $r\geq4$, improving a well-known bound $1-\frac{1}{r}$ of de Caen [Ars Combin., 16 (1983), pp. 5–10] and Sidorenko [Vestnik Moskov. Univ. Ser. I Mat. Mekh., 76 (1982), pp. 3–6].

A Folkman graph is a $K_4$-free graph G such that if the edges of G are 2-colored, then there exists a monochromatic triangle. Erdős offered a prize for proving the existence of a Folkman graph with at most 1 million vertices. In this paper, we construct several “small” Folkman graphs within this limit. In particular, there exists a Folkman graph on 9697 vertices.

We consider the random graph model $G(\mathbf{w})$ for a given expected degree sequence ${\mathbf w} =(w_1, w_2, \ldots, w_n)$. If the expected average degree is strictly greater than 1, then almost surely the giant component in G of $G({\mathbf w})$ has volume (i.e., sum of weights of vertices in the giant component) equal to $\lambda_0 {\rm Vol}(G) + O(\sqrt{n}\log^{3.5} n)$, where $\lambda_0$ is the unique nonzero root of the equation \[ \sum_{i=1}^n w_i e^{-w_i\lambda} = (1-\lambda) \sum_{i=1}^n w_i, \] and where ${\rm Vol}(G)=\sum_i w_i.$

Many massive graphs (such as the WWW graph and Call graphs) share certain universal characteristics which can be described by the so-called "power law." In this paper, we, examine three important aspects of power law graphs, (1) the evolution of power law graphs, (2) the asymmetry of in-degrees and out-degrees, (3) the "scale invariance" of power law graphs. In particular, we give three increasingly general directed graph models and one general undirected graph model for generating power law graphs by adding at most one node and possibly one or more edges at a time. We show that for any given edge density and desired power laws for in-degrees and out-degrees, not necessarily the same, the resulting graph will almost surely have the desired edge density and the power laws for the in-degrees and out-degrees. Our most general directed and undirected models include nearly all known power law evolution models as special cases. Finally, we show that our evolution models generate "scale invariant" graphs. We describe a method for scaling the time in our evolution model such that the power law of the degree sequences remains invariant.

We propose a random graph model which is a special case of sparse random graphs with given degree sequences. This model involves only a small number of parameters, called logsize and log-log growth rate. These parameters capture some universal characteristics of massive graphs. Furthermore, from these parameters, various properties of the graph can be derived. For example, for certain ranges of the parameters, we will compute the expected distribution of the sizes of the connected components which almost surely occur with high probability. We will illustrate the consistency of our model with the behavior of some massive graphs derived from data in telecommunications. We will also discuss the threshold function, the giant component, and the evolution of random graphs in this model. 1 Introduction Is the World Wide Web completely connected? If not, how big is the largest component, the second largest component, etc.? Anyone who has "surfed" the Web for any length of time will come away ...