Search

We consider bond percolation on high-dimensional product graphs $G=\square _{i=1}^tG^{(i)}$ , where $\square$ denotes the Cartesian product. We call the $G^{(i)}$ the base graphs and the product graph $G$ the host graph. Very recently, Lichev (J. Graph Theory , 99(4):651–670, 2022) showed that, under a mild requirement on the isoperimetric properties of the base graphs, the component structure of the percolated graph $G_p$ undergoes a phase transition when $p$ is around $\frac{1}{d}$ , where $d$ is the average degree of the host graph. In the supercritical regime, we strengthen Lichev's result by showing that the giant component is in fact unique, with all other components of order $o(|G|)$ , and determining the sharp asymptotic order of the giant. Furthermore, we answer two questions posed by Lichev (J. Graph Theory , 99(4):651–670, 2022): firstly, we provide a construction showing that the requirement of bounded degree is necessary for the likely emergence of a linear order component; secondly, we show that the isoperimetric requirement on the base graphs can be, in fact, super-exponentially small in the dimension. Finally, in the subcritical regime, we give an example showing that in the case of irregular high-dimensional product graphs, there can be a polynomially large component with high probability, very much unlike the quantitative behaviour seen in the Erdős-Rényi random graph and in the percolated hypercube, and in fact in any regular high-dimensional product graphs, as shown by the authors in a companion paper (Percolation on high-dimensional product graphs. arXiv:2209.03722 , 2022). [ABSTRACT FROM AUTHOR]

In complex network analyses, mainly in social networks, the detection of communities is an important source of information for revealing an internal organization of nodes. On the other hand, if the network reveals a leadership structure, it is possible to understand the mechanisms of information dissemination on it. The detection of leaders and communities is a big challenge depending on the complexity level of the network. In the literature, there are some metaheuristic algorithms for detecting leaders and communities based on pattern recognition on the graph associated with the network. In this paper, we developed a random graph system to generate a synthetic network instance with leader and community structures that define a ground truth. We compare this ground truth to determine the performance of the algorithms LCDA 1 and LCDA 2 for detecting leaders and communities. The results corroborate that the benchmarking system would help in selecting useful configurations for practical applications. [ABSTRACT FROM AUTHOR]

Networks (graphs) permeate scientific fields such as biology, social science, economics, etc. Empirical studies have shown that real-world networks are often heterogeneous, that is, the degrees of nodes do not concentrate on a number. Recently, the Rényi index was tentatively used to measure network heterogeneity. However, the validity of the Rényi index in network settings is not theoretically justified. In this paper, we study this problem. We derive the limit of the Rényi index of a heterogeneous Erdös–Rényi random graph and a power-law random graph, as well as the convergence rates. Our results show that the Erdös–Rényi random graph has asymptotic Rényi index zero and the power-law random graph (highly heterogeneous) has asymptotic Rényi index one. In addition, the limit of the Rényi index increases as the graph gets more heterogeneous. These results theoretically justify the Rényi index is a reasonable statistical measure of network heterogeneity. We also evaluate the finite-sample performance of the Rényi index by simulation. [ABSTRACT FROM AUTHOR]

For graphs G and H , let G ⟶ k H signify that any k -edge coloring of G contains a monochromatic H as a subgraph. Let G (K 2 (N) , p) be random graph spaces with edge probability p , where K 2 (N) is the complete N × N bipartite graph. Let C 2 n be a cycle of length 2 n and let k = 2 , 3. It is shown for any ϵ > 0 , there exists T = T (ϵ) > 0 such that if n p > T , then Pr [ G (K 2 ((k + ϵ) n) , p) ⟶ k C 2 n ] → 1 as n → ∞ , for which the proof relies heavily on the sparse regularity lemma for multipartite graphs. [ABSTRACT FROM AUTHOR]

Anomaly detection of multivariate time series plays a growingly crucial role in intelligent operation and maintenance. Most existing anomaly detection models tend to focus on extracting temporal information while essentially ignoring the relationships among multiple sensors. Graph neural networks simulate multivariate inter-series relationships but suffer from the independent updating of graph structure from data. To overcome such limitation, we present a graph attention network-based model to learn the sensors relationships. It is equipped with a sustainable updating similarity-constrained graph structure learning method and a time series encoder. The graph learning method performs continuous updating of the graph structure. The encoder generates augmented and representative views along the temporal dimension. Our proposed model not only efficiently learns sensor relationships but also improves the ability of anomaly detection. Experiments are performed on publicly benchmark datasets, including SWaT, WADI, and HAI, with F1 scores of 92.98%, 91.19%, and 87.12%, respectively. This confirms that the proposed model outperforms the state-of-the-art in anomaly detection performance. [ABSTRACT FROM AUTHOR]

Document-level relation extraction aims to uncover relations between entities by harnessing the intricate information spread throughout a document. Previous research involved constructing discrete syntactic matrices to capture syntactic relationships within documents. However, these methods are significantly influenced by dependency parsing errors, leaving much of the latent syntactic information untapped. Moreover, prior research has mainly focused on modeling two-hop reasoning between entity pairs, which has limited applicability in scenarios requiring multi-hop reasoning. To tackle these challenges, a syntax-enhanced multi-hop reasoning network (SEMHRN) is proposed. Specifically, the approach begins by using a dependency probability matrix that incorporates richer grammatical information instead of a sparse syntactic parsing matrix to build the syntactic graph. This effectively reduces syntactic parsing errors and enhances the model's robustness. To fully leverage dependency information, dependency-type-aware attention is introduced to refine edge weights based on connecting edge types. Additionally, a part-of-speech prediction task is included to regularize word embeddings. Unrelated entity pairs can disrupt the model's focus, reducing its efficiency. To concentrate the model's attention on related entity pairs, these related pairs are extracted, and a multi-hop reasoning graph attention network is employed to capture the multi-hop dependencies among them. Experimental results on three public document-level relation extraction datasets validate that SEMHRN achieves a competitive F1 score compared to the current state-of-the-art methods. [ABSTRACT FROM AUTHOR]

We study site and bond percolation in simple directed random graphs with a given degree distribution. We derive the percolation threshold for the giant strongly connected component and the fraction of vertices in this component as a function of the percolation probability. The results are obtained for degree sequences in which the maximum degree may depend on the total number of nodes n , being asymptotically bounded by $n^{\frac{1}{9}}$. [ABSTRACT FROM AUTHOR]

In this paper, we consider the friendship paradox in the context of random walks and paths. Among our results, we give an equality connecting long-range degree correlation, degree variability, and the degree-wise effect of additional steps for a random walk on a graph. Random paths are also considered, as well as applications to acquaintance sampling in the context of core-periphery structure. [ABSTRACT FROM AUTHOR]

A well-known open problem on the behavior of optimal paths in random graphs in the strong disorder regime, formulated by statistical physicists, and supported by a large amount of numerical evidence over the last decade (Braunstein et al. in Phys Rev Lett 91(16):168701, 2003; Braunstein et al. in Int J Bifurc Chaos 17(07):2215–2255, 2007; Chen et al. in Phys Rev Lett 96(6):068702, 2006; Wu et al. in Phys Rev Lett 96(14):148702, 2006) is as follows: for a large class of random graph models with degree exponent τ ∈ (3 , 4) , distances in the minimal spanning tree (MST) on the giant component in the supercritical regime scale like n (τ - 3) / (τ - 1) . The aim of this paper is to make progress towards a proof of this conjecture. We consider a supercritical inhomogeneous random graph model with degree exponent τ ∈ (3 , 4) that is closely related to Aldous's multiplicative coalescent, and show that the MST constructed by assigning i.i.d. continuous weights to the edges in its giant component, endowed with the tree distance scaled by n - (τ - 3) / (τ - 1) , converges in distribution with respect to the Gromov–Hausdorff topology to a random compact real tree. Further, almost surely, every point in this limiting space either has degree one (leaf), or two, or infinity (hub), both the set of leaves and the set of hubs are dense in this space, and the Minkowski dimension of this space equals (τ - 1) / (τ - 3) . The multiplicative coalescent, in an asymptotic sense, describes the evolution of the component sizes of various near-critical random graph processes. We expect the limiting spaces in this paper to be the candidates for the scaling limit of the MST constructed for a wide array of other heavy-tailed random graph models. [ABSTRACT FROM AUTHOR]

Given a labeled tree topology t , consider a population P of k leaves chosen among those of t. The clade of P is the minimal subtree of t containing P and its size is given by the number of leaves in the clade. When t is selected under the Yule or uniform distribution among the labeled topologies of size n , we study the "clade size" random variable determining closed formulas for its probability mass function, its mean, and its variance. Our calculations show that for large n the clade size tends to be smaller under the uniform model than under the Yule model, with a larger variability in the first scenario for values of k ≥ 5. We apply our probability formulas to investigate set-theoretic relationships between the clades of two populations in a random tree, determining how likely one clade is contained in or it is equal to the other. Our study relates to earlier calculations for the probability that under the Yule model the clade size of P equals the size of P – that is, the population P forms a monophyletic group – and extends known results for the probability that the minimal (non-trivial) clade containing a random taxon has a given size. [ABSTRACT FROM AUTHOR]

A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach nongeometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs. [ABSTRACT FROM AUTHOR]

The voter model is a classical interacting particle system, modeling how global consensus is formed by local imitation. We analyze the time to consensus for a particular family of voter models when the underlying structure is a scale-free inhomogeneous random graph in the high edge-density regime, where this graph features a giant component. In this regime, we verify that the polynomial orders of consensus agree with those of their mean-field approximation in [A. Moinet, A. Barrat, and R. Pastor-Satorras, Phys. Rev. E, 98 (2018), 022303]. This "discursive" family of models has a symmetrized interaction to better model discussions and is indexed by a temperature parameter that, for certain parameters of the power law tail of the network's degree distribution, is seen to produce two distinct phases of consensus speed. Our proofs rely on the well-known duality to coalescing random walks and a novel bound on the mixing time of these walks using the known fast mixing of the Erdös-Rényi giant subgraph. Unlike in the subcritical case [J. Fernley and M. Ortgiese, Random Structures Algorithms, 62 (2023), pp. 376-429], which requires tail exponent of the limiting degree distribution τ = 1 +1/γ > 3 as well as low edge density, in the giant component case, we also address the "ultrasmall world" power law exponents τ ∈ (2,3]. [ABSTRACT FROM AUTHOR]

We describe a robust methodology, based on the martingale argument of Nachmias and Peres and random walk estimates, to obtain simple upper and lower bounds on the size of a maximal component in several random graphs at criticality. Even though the main result is not new, we believe the material presented here is interesting because it unifies several proofs found in the literature into a common framework. More specifically, we give easy-to-check conditions that, when satisfied, allow an immediate derivation of the above-mentioned bounds. [ABSTRACT FROM AUTHOR]

Graph processes that unfold in continuous time are of obvious theoretical and practical interest. Particularly useful are those whose long-term behavior converges to a graph distribution of known form. Here, we review some of the conditions for such convergence, and provide examples of novel and/or known processes that do so. These include subfamilies of the well-known stochastic actor-oriented models, as well as continuum extensions of temporal and separable temporal exponential family random graph models. We also comment on some related threads in the broader work on network dynamics, which provide additional context for the continuous time case. [ABSTRACT FROM AUTHOR]

The object of study is a soft random geometric graph with vertices given by a Poisson point process on a line and edges between vertices present with probability that has a polynomial decay in the distance between them. Various aspects of such models related to connectivity structures have been studied extensively. In this article, we study the random graph from the perspective of extreme value theory and focus on the occurrence of single long edges. The model we investigate has non-periodic boundary and is parameterized by a positive constant α, which is the power for the polynomial decay of the probabilities determining the presence of an edge. As a main result, we provide a precise description of the magnitude of the longest edge in terms of asymptotic behavior in distribution. Thereby we illustrate a crucial dependence on the power α and we recover a phase transition which coincides with exactly the same phases in Benjamini and Berger. [ABSTRACT FROM AUTHOR]

Background: Existing research has demonstrated that student characteristics, such as race/ethnicity, sex, and personal beliefs about engineering knowledge, shape students' experiences in ill‐structured problem‐solving, such as engineering design, where ideas must be communicated, negotiated, and selected in complex social processes. Purpose: The purpose of this research was to examine the how student characteristics, such as race/ethnicity, sex, and epistemological beliefs, are associated with patterns of idea contributions and ideas enactments in collaborative project teams. Method: In this article, I use the multilayer exponential random graph model (ERGM) for examining multiple complex social relationships simultaneously. Drawing on survey data from a study of engineering student teamwork, this research examines the relationship perceptions of idea contributions (layer 1) and idea enactments (layer 2) in collaborative project teams. Results: Results indicated no sex differences in the perceptions of idea contributions and enactments in student design teams. However, underrepresented minority students and Asian America/Pacific Islander students were reported as less frequently having their ideas enacted. Further, epistemological beliefs similarity effects were a significant predictor on the idea contribution layer, and epistemological beliefs sociality effects were significant on the idea enactments layer. Conclusion: Achieving equity in teamwork pedagogies requires understanding the dynamic social processes that shapes patterns of participation in student teams. This research demonstrates the power of social networks methodologies for modeling teamwork processes, pointing specifically to the ways that student characteristics are associated with perceptions shape idea contributions and enactments in student teams. [ABSTRACT FROM AUTHOR]

The problem of how to attract a robust following on social media is one of the most pressing for influencers. We study a common practice on popular microblogging platforms such as Twitter, of influencers' expanding their followings by running lotteries and giveaways. We are interested in how the lottery size and the seeding decisions influence the information propagation and the final reward for such a campaign. We construct an information-diffusion model based on a random graph, and show that the market demand curve of the lottery reward via the promotion of the social network is "S"-shaped. This property lays a foundation for finding the optimal lottery size. Second, we observe that (i) dynamic seeding could re-stimulate the spread of information and (ii) with a fixed budget, seeding at two fixed occasions is always better than seeding once at the beginning. This observation motivates us to study the joint optimization of lottery size and adaptive seeding. We model the adaptive seeding problem as a Markov Decision Process. We find the monotonicity of the value functions and trends in the optimal actions, and we show that with adaptive seeding, the reward curve is approximately "S"-shaped with respect to the lottery size. [ABSTRACT FROM AUTHOR]

We prove that the size of the maximum induced forest (of bounded and unbounded degree) in the binomial random graph for with an arbitrary fixed is concentrated in an interval of size . We also show 2-point concentration for the size of the maximum induced forest (and tree) of bounded degree in for p = const. [ABSTRACT FROM AUTHOR]

In this note, we solve the "birthday problem" for loops on random regular graphs. Namely, for fixed d≥3 $d\ge 3$, we prove that on a random d $d$‐regular graph with n $n$ vertices, as n $n$ approaches infinity, with high probability: (i) almost all primitive nonbacktracking loops of length k≺n $k\prec \sqrt{n}$ are simple, that is, do not self‐intersect, and (ii) almost all primitive nonbacktracking loops of length k≺n $k\prec \sqrt{n}$ self‐intersect. [ABSTRACT FROM AUTHOR]

We show that the threshold for having a rainbow copy of a power of a Hamilton cycle in a randomly edge colored copy of Gn,p ${G}_{n,p}$ is within a constant factor of the uncolored threshold. Our proof requires (1+ε) $(1+\varepsilon)$ times the minimum number of colors. [ABSTRACT FROM AUTHOR]

In the last two decades, we are witnessing a huge increase of valuable big data structured in the form of graphs or networks. To apply traditional machine learning and data analytic techniques to such data it is necessary to transform graphs into vector‐based representations that preserve the most essential structural properties of graphs. For this purpose, a large number of graph embedding methods have been proposed in the literature. Most of them produce general‐purpose embeddings suitable for a variety of applications such as node clustering, node classification, graph visualization and link prediction. In this article, we propose two novel graph embedding algorithms based on random walks that are specifically designed for the node classification problem. Random walk sampling strategies of the proposed algorithms have been designed to pay special attention to hubs–high‐degree nodes that have the most critical role for the overall connectedness in large‐scale graphs. The proposed methods are experimentally evaluated by analyzing the classification performance of three classification algorithms trained on embeddings of real‐world networks. The obtained results indicate that our methods considerably improve the predictive power of examined classifiers compared with currently the most popular random walk method for generating general‐purpose graph embeddings (node2vec). [ABSTRACT FROM AUTHOR]

Many real-world networks exhibit the phenomenon of edge clustering,which is typically measured by the average clustering coefficient. Recently,an alternative measure, the average closure coefficient, is proposed to quantify local clustering. It is shown that the average closure coefficient possesses a number of useful properties and can capture complementary information missed by the classical average clustering coefficient. In this paper, we study the asymptotic distribution of the average closure coefficient of a heterogeneous Erdős–Rényi random graph. We prove that the standardized average closure coefficient converges in distribution to the standard normal distribution. In the Erdős–Rényi random graph,the variance of the average closure coefficient exhibits the same phase transition phenomenon as the average clustering coefficient. [ABSTRACT FROM AUTHOR]

The exponential random graph model (ERGM) is a central object in the study of clustering properties in social networks as well as canonical ensembles in statistical physics. Despite some breakthrough works in the mathematical understanding of ERGM, most notably by Bhamidi, Bresler, and Sly [Ann. Appl. Probab. 21 (2011), pp. 2146–2170] through the analysis of a natural Heat-bath Glauber dynamics, and by Chatterjee and Diaconis [Ann. Statist. 41 (2013), pp. 2428–2461; Eldan [Geom. Funct. Anal. 28 (2018), pp. 1548–1596; and Eldan and Gross [Ann. Appl. Probab. 28 (2018), pp. 3698–3735] via a large deviation theoretic perspective, several basic questions have remained unanswered owing to the lack of exact solvability unlike the much studied Curie-Weiss model (Ising model on the complete graph). In this paper, we establish a series of new concentration of measure results for the ERGM throughout the entire sub-critical phase , including a Poincaré inequality, Gaussian concentration for Lipschitz functions, and a central limit theorem. In addition, a new proof of a quantitative bound on the W_1-Wasserstein distance to Erdős-Rényi graphs, previously obtained by Reinert and Ross [Ann. Appl. Probab. 29 (2019), pp. 3201–3229], is also presented. The arguments rely on translating temporal mixing properties of Glauber dynamics to static spatial mixing properties of the equilibrium measure and have the potential of being useful in proving similar functional inequalities for other Gibbsian systems beyond the perturbative regime. [ABSTRACT FROM AUTHOR]

We investigate whether it is possible to distinguish chaotic time series from random time series using network theory. In this perspective, we selected four methods to generate graphs from time series: the natural, the horizontal, the limited penetrable horizontal visibility graph, and the phase space reconstruction method. These methods claim that the distinction of chaos from randomness is possible by studying the degree distribution of the generated graphs. We evaluated these methods by computing the results for chaotic time series from the 2D Torus Automorphisms, the chaotic Lorenz system, and a random sequence derived from the normal distribution. Although the results confirm previous studies, we found that the distinction of chaos from randomness is not generally possible in the context of the above methodologies. [ABSTRACT FROM AUTHOR]

In this paper we study acyclic colouring in the random subgraph G of the complete graph Kn on n vertices where each edge is present with probability p, independent of the other edges. We show that unlike the ordinary chromatic number, the acyclic chromatic number exhibits a phase transition from sub-linear to linear growth as the edge probability increases, even in the sparse regime and obtain estimates for the critical exponent. We show that allowing for a small relaxation in the acyclic colouring condition allows for sub-linear growth for all values of the edge probability exponent. We also study a generalization of unique colourings where we impose the condition that at least one vertex in any copy of a given tree has a unique colour and obtain bounds for the minimum number of colours needed for such a colouring. [ABSTRACT FROM AUTHOR]

The Eulerian extension number of any graph H (i.e. the minimum number of edges needed to be added to make H Eulerian) is at least t(H), half the number of odd degree vertices of H. In this paper we consider weighted Eulerian extensions of a random graph G where we add edges of bounded weights and use an iterative probabilistic method to obtain sufficient conditions for the weighted Eulerian extension number of G to grow linearly with t(G). We derive our conditions in terms of the average edge probabilities and edge density and also show that bounded extensions are rare by estimating the skewness of a fixed weighted extension. Finally, we briefly describe a decomposition involving Eulerian extensions of G to convert a large dataset into small dissimilar batches. [ABSTRACT FROM AUTHOR]

The k-spectrum is the set of all α > 0 such that G(n,n−α) does not obey the 0-1 law for FO sentences with quantifier depth at most k. In this article, we prove that the minimum k such that the k-spectrum is infinite equals 5. [ABSTRACT FROM AUTHOR]

We show that the threshold for having a rainbow copy of a power of a Hamilton cycle in a randomly edge colored copy of Gn,p ${G}_{n,p}$ is within a constant factor of the uncolored threshold. Our proof requires (1+ε) $(1+\varepsilon)$ times the minimum number of colors. [ABSTRACT FROM AUTHOR]

We study the extent to which it is possible to approximate the optimal value of a Unique Games instance in Fixed-Point Logic with Counting (FPC). Formally, we prove lower bounds against the accuracy of FPC-interpretations that map Unique Games instances (encoded as relational structures) to rational numbers giving the approximate fraction of constraints that can be satisfied. We prove two new FPC-inexpressibility results for Unique Games: the existence of a (1/2, 1/3 + δ)-inapproximability gap, and inapproximability to within any constant factor. Previous recent work has established similar FPC-inapproximability results for a small handful of other problems. Our construction builds upon some of these ideas, but contains a novel technique. While most FPCinexpressibility results are based on variants of the CFI-construction, ours is significantly different. We start with a graph of very large girth and label the edges with random affine vector spaces over F2 that determine the constraints in the two structures. Duplicator’s strategy involves maintaining a partial isomorphism over a minimal tree that spans the pebbled vertices of the graph. [ABSTRACT FROM AUTHOR]

Graph clustering is an important problem in network analysis. This problem can be approached by first finding a large cluster subgraph (i.e., a subgraph in which every connected component is a complete graph), perhaps in a relaxed form (connected components may have missing edges), and then assigning each of the remaining vertices to one of the connected components of the cluster subgraph according to some optimization criteria. The more vertices can be included in the initial cluster subgraph (also referred to as independent union of clusters), the more "clusterable" the graph is. This paper proposes a framework for establishing asymptotic bounds on the cardinality of independent unions of clusters in Erdős‐Rényi random graphs G(n,p)$$ G\left(n,p\right) $$ with constant p$$ p $$, referred to as uniform random graphs. In particular, sufficient conditions ensuring O(logn)$$ O\left(\log n\right) $$ (where n$$ n $$ is the number of nodes) upper bounds with probability 1 are developed and shown to be applicable for the maximum independent union of cliques as well as some clique relaxations. In addition, it is shown that every graph must have an independent union of cliques of cardinality at least Ω(logn)$$ \Omega \left(\log n\right) $$. Since this bound is asymptotically tight on uniform random graphs, this suggests that these graphs can be viewed as a "least clusterable" class of graphs. [ABSTRACT FROM AUTHOR]

Although robustness of connectivity and modular structures in networks have been attracted much attentions in complex networks, most researches have focused on those two features in Erdos-Renyi random graphs and Scale-Free networks whose degree distributions follow Poisson and power-law, respectively. This paper investigates the effect of modularity on robustness in a modular d-regular graphs. Our results reveal that high modularity reduces the robustness even from the optimal robustness of a random d-regular graph in the pure effect of degree distributions. Moreover, we find that a low modular d-regular graph exhibits small-world property that average path length is O(logN). These results indicate that low modularity on modular structures leads to coexistence of both high robustness and efficiency of paths. [ABSTRACT FROM AUTHOR]

This article delves into the analysis and identification of influential individuals within social networks, a fundamental issue in the realm of social network science and complex network analysis. Within social networks, the impact of individuals on information propagation, shaping beliefs, and influencing the behavior of others is of paramount importance. Most of the current methods are based on the assumption that the entire graph is visible. However, this assumption does not hold for many real-world graphs. This study is conducted to extend current maximization methods, with link prediction techniques to pseudo-visibility graphs. The proposed method in this paper leverages graph models and influence algorithms to identify and select influential individuals within a social network. It begins by employing graph models to predict connections within the network and subsequently employs influence algorithms to opt for the most suitable individuals for exerting influence within the network. The primary advantage of this approach lies in its capability to enhance communication and influence within social networks with minimal observation. This method aids in a better understanding of the network's structure and the behaviors of its members, ultimately facilitating more effective information dissemination. In this study, we implemented five concepts for influence maximization in the context of the proposed method. Our results indicate that the algorithms perform best when considering lower diffusion coefficients. This suggests that focusing on lower diffusion coefficients allows the algorithm to demonstrate its superiority. Additionally, our findings reveal a notable consistency in results across various graph removal scenarios, highlighting a key advantage of our proposed approach on real-world graphs. [ABSTRACT FROM AUTHOR]

Hyperspectral image has excellent spectral information and abundant spatial information, and its feature quality is one of the key factors affecting the classification performance. Extreme learning machine (ELM) is widely used in hyperspectral classification problems. However, traditional ELM is usually based on regular Euclidean data, ignoring the inherent structured information between hyperspectral pixels, resulting in poor robustness. In this paper, we propose a new supervised extreme learning machine framework, termed spatial-spectral graph convolutional ELM (SSG-ELM), based on using graph convolution to extend ELM into the non-Euclidean domain. The method inherits all the advantages from ELM, and consists of a random graph convolutional layer followed by a graph convolutional regression layer, enabling it to model complex intra class variations. Otherwise, a local spectral-spatial context integration and reshaping mechanism is incorporated into the hidden layer feature representation by using a context-aware bilateral filtering procedure. Experimental results show that the proposed algorithm obtains a competitive performance and outperforms other state-of-the-art ELM-based methods. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph on n vertices, and let G σ be an orientation of G with skew adjacency matrix S (G σ). Let d i be the degree of the vertex v i in G. The skew Randić matrix of G σ is the n × n real skew symmetric matrix R S (G σ) = [ (R S) i j ] , where (R S) i j = − (R S) j i = (d i d j) − 1 2 if (v i , v j) is an arc of G σ , and (R S) i j = (R S) j i = 0 otherwise. The skew spectral radius ρ S (G σ) and the skew Randić spectral radius ρ R S (G σ) of G σ are defined as the spectral radius of S (G σ) and R S (G σ) respectively. In this paper we give upper bounds for the skew spectral radius and skew Randić spectral radius of general random oriented graphs. [ABSTRACT FROM AUTHOR]

In the edge-triangle model with edge density close to 1/2 and triangle density below 1/8 we prove that the unique entropy-maximizing graphon is symmetric bipodal. We also prove that, for any edge density e less than e 0 = (3 − 3) / 6 ≈ 0.2113 and triangle density slightly less than e 3, the entropy-maximizing graphon is not symmetric bipodal. We also discuss the implications for an old idea of Landau for using symmetry to give an intrinsic difference between solid and fluid phases of matter. [ABSTRACT FROM AUTHOR]

In the context of community detection, correlation clustering (CC) provides a measure of balance for social networks as well as a tool to explore their structures. However, CC does not encompass features such as the mediation between the clusters, which could be all the more relevant with the recent rise of ideological polarization. In this work, we study correlation clustering under mediation (CCM), a new variant of CC in which a set of mediators is determined. This new signed graph clustering problem is proved to be NP-hard and formulated as an integer programming formulation. An extensive investigation of the mediation set structure leads to the development of two efficient exact enumeration algorithms for CCM. The first one exhaustively enumerates the maximal sets of mediators in order to provide several relevant solutions. The second algorithm implements a pruning mechanism, which drastically reduces the size of the exploration tree in order to return a single optimal solution. Computational experiments are presented on two sets of instances: signed networks representing voting activity in the European Parliament and random signed graphs. History: Accepted by Van Hentenryck, Area Editor for Pascal. Funding: This work was supported by Fondation Mathématique Jacques Hadamard [Grant P-2019-0031]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0129) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0129). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Numerous investigations increasingly indicate the significance of microRNA (miRNA) in human diseases. Hence, unearthing associations between miRNA and diseases can contribute to precise diagnosis and efficacious remediation of medical conditions. The detection of miRNA-disease linkages via computational techniques utilizing biological information has emerged as a cost-effective and highly efficient approach. Here, we introduced a computational framework named ReHoGCNES, designed for prospective miRNA-disease association prediction (ReHoGCNES-MDA). This method constructs homogenous graph convolutional network with regular graph structure (ReHoGCN) encompassing disease similarity network, miRNA similarity network and known MDA network and then was tested on four experimental tasks. A random edge sampler strategy was utilized to expedite processes and diminish training complexity. Experimental results demonstrate that the proposed ReHoGCNES-MDA method outperforms both homogenous graph convolutional network and heterogeneous graph convolutional network with non-regular graph structure in all four tasks, which implicitly reveals steadily degree distribution of a graph does play an important role in enhancement of model performance. Besides, ReHoGCNES-MDA is superior to several machine learning algorithms and state-of-the-art methods on the MDA prediction. Furthermore, three case studies were conducted to further demonstrate the predictive ability of ReHoGCNES. Consequently, 93.3% (breast neoplasms), 90% (prostate neoplasms) and 93.3% (prostate neoplasms) of the top 30 forecasted miRNAs were validated by public databases. Hence, ReHoGCNES-MDA might serve as a dependable and beneficial model for predicting possible MDAs. [ABSTRACT FROM AUTHOR]

The development and widespread utilization of high-throughput sequencing technologies in biology has fueled the rapid growth of single-cell RNA sequencing (scRNA-seq) data over the past decade. The development of scRNA-seq technology has significantly expanded researchers' understanding of cellular heterogeneity. Accurate cell type identification is the prerequisite for any research on heterogeneous cell populations. However, due to the high noise and high dimensionality of scRNA-seq data, improving the effectiveness of cell type identification remains a challenge. As an effective dimensionality reduction method, Principal Component Analysis (PCA) is an essential tool for visualizing high-dimensional scRNA-seq data and identifying cell subpopulations. However, traditional PCA has some defects when used in mining the nonlinear manifold structure of the data and usually suffers from over-density of principal components (PCs). Therefore, we present a novel method in this paper called joint L 2 , p -norm and random walk graph constrained PCA (RWPPCA). RWPPCA aims to retain the data's local information in the process of mapping high-dimensional data to low-dimensional space, to more accurately obtain sparse principal components and to then identify cell types more precisely. Specifically, RWPPCA combines the random walk (RW) algorithm with graph regularization to more accurately determine the local geometric relationships between data points. Moreover, to mitigate the adverse effects of dense PCs, the L 2 , p -norm is introduced to make the PCs sparser, thus increasing their interpretability. Then, we evaluate the effectiveness of RWPPCA on simulated data and scRNA-seq data. The results show that RWPPCA performs well in cell type identification and outperforms other comparison methods. [ABSTRACT FROM AUTHOR]

A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdös--Rényi random graph, G - Gn,p, by considering a random permutation π of the edges and interpreting the ranks in π as presence times. We give a thorough study of the temporal connectivity of such graphs and derive implications for the existence of several kinds of sparse spanners. It turns out that temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at p = log n/n, any fixed pair of vertices can asymptotically almost surely (a.a.s.) reach each other; at 2 log n/n, at least one vertex (and, in fact, any fixed vertex) can a.a.s. reach all others; and at 3 log n/n, all the vertices can a.a.s. reach each other; i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size 2n + o(n) as soon as it becomes temporally connected, which is nearly optimal, as 2n - 4 is a lower bound. This result is quite significant because temporal graphs do not admit spanners of size O(n) in general [Kempe, Kleinberg, and Kumar, J. Comput. System Sci., 64 (2002), pp. 820--842]. In fact, they do not even always admit spanners of size o(n²) [Axiotis and Fotakis, On the size and the approximability of minimum temporally connected subgraphs, 2016, pp. 149:1--149:14]. Thus, our result implies that the obstructions found in these works---and more generally any non-negligible obstruction---are statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners a step further, we show that pivotal spanners---i.e., spanners of size 2n - 2 composed of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently)---exist a.a.s. at 4 log n/n, this threshold being also sharp. Finally, we show that optimal spanners (of size 2n - 4) also exist a.a.s. at p = 4 log n/n. Whether this value is a sharp threshold is open; we conjecture that it is. For completeness, we compare the above results to existing results in related areas, including edge- ordered graphs, gossip theory, and population protocols, showing that our results can be interpreted in these settings as well and that in some cases they improve known results therein. Finally, we discuss an intriguing connection between our results and Janson's celebrated results on percolation in weighted graphs. [ABSTRACT FROM AUTHOR]

Chinese city governments have collaborated increasingly to address regional environmental issues by participating in informal and formal collaborative networks. However, collaboration among cities involves collaboration risks. This study investigates how cities strategically select collaborative partners in informal and formal networks in the context of the Yangtze River Delta in China. This study addresses this question by assessing the nature of collaborative problems in the informal and formal networks, the extent of homophily in actors' preferences, and their relationship multiplexity. Findings from Exponential Random Graph Analysis demonstrate: (1) city governments tend to connect to the popular actor and create relationship closure in the informal network, while only forging relationship closure in the formal network; (2) homophily (in water pollution) and heterogeneity (in air pollution) jointly affect city governments' choices of collaborative partners in the formal network; and (3) the presence of relationship multiplexity wherein the formation of formal ties is built between city governments with pre-existing informal interactions. The findings advance our knowledge of collaborative partner selection and local collaborative governance in China. [ABSTRACT FROM AUTHOR]

We study the distances of vertices within cliques in a soft random geometric graph on a torus, where the vertices are points of a homogeneous Poisson point process, and far-away points are less likely to be connected than nearby points. We obtain the scaling of the maximal distance between any two points within a clique of size k. Moreover, we show that asymptotically in all cliques with large distances, there is only one remote point and all other points are nearby. Furthermore, we prove that a re-scaled version of the maximal k-clique distance converges in distribution to a Fréchet distribution. Thereby, we describe the order of magnitude according to which the largest distance between two points in a clique decreases with the clique size. [ABSTRACT FROM AUTHOR]

We propose a penalized conditional likelihood criterion to estimate the basic neighborhood of each node in a discrete Markov random field that can be partially observed. We prove the convergence of the estimator in the case of a finite or countable infinite set of nodes. The estimated neighborhoods can be combined to estimate the underlying graph. In the finite case, the graph can be recovered with probability one. In contrast, we can recover any finite subgraph with probability one in the countable infinite case by allowing the candidate neighborhoods to grow as a function o(logn)$$ o\left(\log n\right) $$, with n$$ n $$ the sample size. Our method requires minimal assumptions on the probability distribution, and contrary to other approaches in the literature, the usual positivity condition is not needed. We evaluate the estimator's performance on simulated data and apply the methodology to a real dataset of stock index markets in different countries. [ABSTRACT FROM AUTHOR]

Next generation wireless communication (WC) needs high-performance which assist high-speed data transmission while meeting the requirements for low profile, weight and cost. Several researchers introduce graphene-based circular, triangular, square and hexagonal antenna for WC in the terahertz (THz) resonant frequency (RF). This research work introduces a deep graphene based reconfigurable circularly polarized star-shaped microstrip antenna at 2.98 THz frequency for biomedical application. Graphene has been applied in the structure of star-shaped microstrip antenna. This reconfigurable circularly polarized graphene-based antenna is obtained on a SiO2 substrate. The introduced circularly polarized antenna has a single feed and an easy design. The major objective of this research work is to propose graphene material as an efficient solution in designing antenna for organizing and adjusting its polarization. Because of the complexity of the structure of graphene antenna, enhanced scalable graph random improved Fick's law neural networks is applied for predicting the antenna parameters. This proposed method is a combination of enhanced scalable graph random neural network (ESGRNN) and an improved Fick's law optimization which is used to optimize the prediction error of the proposed ESGRNN. To prevent premature incomplete convergence in the traditional Fick's law algorithm, a dynamic lens-imaging learning strategy is incorporated. Finally, the achieved prediction accuracy is 98%, the mean square error is 2%, minimal return loss (S11) is − 55.98 dB, impedance bandwidth is 800 GHz, gain is 9.8 dB, and voltage standing wave ratio is 1.011 at 2.98 THz RF. As a result, the designed antenna is well-suitable for biomedical applications like riboflavin detection. [ABSTRACT FROM AUTHOR]

The average-case complexity of a branch-and-bound algorithm for Min Dominating Set problem in random graphs in the G (n , p) model is studied. We identify phase transitions between subexponential and exponential average-case complexities, depending on the growth of the probability p with respect to the number n of nodes. [ABSTRACT FROM AUTHOR]

The notion of spectrum for first-order properties introduced by J. Spencer for Erdős–Rényi random graph is considered in relation to random uniform hypergraphs. In this work we study the set of limit points of the spectrum for first-order formulae with bounded quantifier depth and obtain bounds for its maximum value. Moreover, we prove zero–one k -laws for the random uniform hypergraph and improve the bounds for the maximum value of the spectrum for first-order formulae with bounded quantifier depth. We obtain that the maximum value of the spectrum belongs to some two-element set. [ABSTRACT FROM AUTHOR]

We consider a class of weakly interacting particle systems of mean-field type. The interactions between the particles are encoded in a graph sequence, i.e. two particles are interacting if and only if they are connected in the underlying graph. We establish a law of large numbers for the empirical measure of the system that holds whenever the graph sequence is convergent to a graphon. The limit is the solution of a non-linear Fokker–Planck equation weighted by the (possibly random) graphon limit. In contrast with the existing literature, our analysis focuses on both deterministic and random graphons: no regularity assumptions are made on the graph limit and we are able to include general graph sequences such as exchangeable random graphs. Finally, we identify the sequences of graphs, both random and deterministic, for which the associated empirical measure converges to the classical McKean–Vlasov mean-field limit. [ABSTRACT FROM AUTHOR]

We study competing first passage percolation on graphs generated by the configuration model with infinite-mean degrees. Initially, two uniformly chosen vertices are infected with a type 1 and type 2 infection, respectively, and the infection then spreads via nearest neighbors in the graph. The time it takes for the type 1 (resp. 2) infection to traverse an edge e is given by a random variable $X_1(e)$ (resp. $X_2(e)$) and, if the vertex at the other end of the edge is still uninfected, it then becomes type 1 (resp. 2) infected and immune to the other type. Assuming that the degrees follow a power-law distribution with exponent $\tau \in (1,2)$ , we show that with high probability as the number of vertices tends to infinity, one of the infection types occupies all vertices except for the starting point of the other type. Moreover, both infections have a positive probability of winning regardless of the passage-time distribution. The result is also shown to hold for the erased configuration model, where self-loops are erased and multiple edges are merged, and when the degrees are conditioned to be smaller than $n^\alpha$ for some $\alpha\gt 0$. [ABSTRACT FROM AUTHOR]

Team and individual incentives are ubiquitous in sales, but little is known about their impact on collaboration when they are applied simultaneously. The presence of both types of incentives creates a "coopetitive" environment, where forces of collaboration and competition coexist. We examine how such environments impact the likelihood (Study 1) and the effectiveness (Study 2) of collaboration in the form of advice exchange. Exponential random graph modeling (ERGM) of network data of 540 salespeople reveals that individual incentives promote advice seeking but discourage advice giving, and team incentives stimulate advice giving but reduce advice seeking (Study 1). We also find that the effectiveness of advice depends on advice givers (Study 2). In particular, when advice givers have diverse team incentives, the advice is more effective and the need for additional advice is reduced, but when advice givers have diverse individual incentives, the advice is less effective and additional advice helps. [ABSTRACT FROM AUTHOR]

Consider the normalized adjacency matrices of random d‐regular graphs on N vertices with fixed degree d⩾3$d\geqslant 3$. We prove that, with probability 1−N−1+ε$1-N^{-1+\varepsilon }$ for any ε>0$\varepsilon >0$, the following two properties hold as N→∞$N \rightarrow \infty$ provided that d⩾3$d\geqslant 3$: (i) The eigenvalues are close to the classical eigenvalue locations given by the Kesten–McKay distribution. In particular, the extremal eigenvalues are concentrated with polynomial error bound in N, that is, λ2,|λN|⩽2+N−c$\lambda _2, |\lambda _N|\leqslant 2+N^{-c}$. (ii) All eigenvectors of random d‐regular graphs are completely delocalized. [ABSTRACT FROM AUTHOR]

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry‐invariant? This question was answered for one‐ended unimodular graphs in Benjamini and Timar, using the fact that such graphs automatically have locally finite (simply connected) drawings into the plane. For the case of graphs with multiple ends the question was left open. We revisit Halin's graph theoretic characterization of graphs that have a locally finite embedding into the plane. Then we prove that such unimodular random graphs do have a locally finite invariant embedding into the Euclidean or the hyperbolic plane, depending on whether the graph is amenable or not. [ABSTRACT FROM AUTHOR]