More Like this

1. Chained structure of directed graphs with applications to social and transportation networks

   https://doi.org/10.1007/s41109-022-00502-x  

   Concas, Anna ; Fenu, Caterina ; Reichel, Lothar ; Rodriguez, Giuseppe ; Zhang, Yunzi ( September 2022 , Applied Network Science)

   The need to determine the structure of a graph arises in many applications. This paper studies directed graphs and defines the notions of$$\ell$$$\ell$-chained and$$\{\ell ,k\}$$$\{\ell ,k\}$-chained directed graphs. These notions reveal structural properties of directed graphs that shed light on how the nodes of the graph are connected. Applications include city planning, information transmission, and disease propagation. We also discuss the notion of in-center and out-center vertices of a directed graph, which are vertices at the center of the graph. Computed examples provide illustrations, among which is the investigation of a bus network for a city.

    

   more » « less
2. On Weak Flexibility in Planar Graphs

   https://doi.org/10.1007/s00373-022-02564-1  

   Lidický, Bernard ; Masařík, Tomáš ; Murphy, Kyle ; Zerbib, Shira ( December 2022 , Graphs and Combinatorics)

   Abstract Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447 ). In this new setting, each vertex v in some subset of V ( G ) has a request for a certain color r ( v ) in its list of colors L ( v ). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon >0$$ ε > 0 such that any graph G in some graph class $$\mathscr {C}$$ C satisfies at least $$\varepsilon$$ ε proportion of the requests. More formally, for $$k > 0$$ k > 0 the goal is to prove that for any graph $$G \in \mathscr {C}$$ G ∈ C on vertex set V , with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ R ⊆ V and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ ( r ( v ) : v ∈ R , r ( v ) ∈ L ( v ) ) , there exists an L -coloring of G satisfying at least $$\varepsilon |R|$$ ε | R | requests. If this is true, then $$\mathscr {C}$$ C is called $$\varepsilon$$ ε - flexible for lists of size k . Choi, Clemen, Ferrara, Horn, Ma, and Masařík (Discrete Appl Math 306:20–132, 2022, https://doi.org/10.1016/j.dam.2021.09.021 ) introduced the notion of weak flexibility , where $$R = V$$ R = V . We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b there exists $$\varepsilon (b)>0$$ ε ( b ) > 0 so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$ K 4 , C 5 , C 6 , C 7 , B b is weakly $$\varepsilon (b)$$ ε ( b ) -flexible for lists of size 4 (here $$K_n$$ K n , $$C_n$$ C n and $$B_n$$ B n are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$ K 4 , C 5 , C 6 , C 7 , B 5 is $$\varepsilon$$ ε -flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable. 

   more » « less
3. Finding Cliques in Social Networks: A New Distribution-Free Model

   Fox, James ; Roughgarden, Tim ; Seshadhri, C ; Wei, Fan and ( July 2018 , SIAM journal on computing)

   This paper proposes a new distribution-free model of social networks. The definitions are motivated by one of the most universal signatures of social networks, triadic closure—the property that pairs of vertices with common neighbors tend to be adjacent. Our most basic definition is that of a c-closed graph, where for every pair of vertices u, v with at least c common neighbors, u and v are adjacent. We study the classic problem of enumerating all maximal cliques, an important task in social network analysis. We prove that this problem is fixed-parameter tractable with respect to c on c-closed graphs. Our results carry over to weakly c-closed graphs, which only require a vertex deletion ordering that avoids pairs of non-adjacent vertices with c common neighbors. Numerical experiments show that well-studied social networks with thousands of vertices tend to be weakly c-closed for modest values of c. 

   more » « less
4. BC tree-based spectral sampling for big complex network visualization

   https://doi.org/10.1007/s41109-021-00405-3  

   Hu, Jingming ; Chu, Tuan Tran ; Hong, Seok-Hee ; Chen, Jialu ; Meidiana, Amyra ; Torkel, Marnijati ; Eades, Peter ; Ma, Kwan-Liu ( December 2021 , Applied Network Science)

   Abstract Graph sampling methods have been used to reduce the size and complexity of big complex networks for graph mining and visualization. However, existing graph sampling methods often fail to preserve the connectivity and important structures of the original graph. This paper introduces a new divide and conquer approach to spectral graph sampling based on graph connectivity, called the BC Tree (i.e., decomposition of a connected graph into biconnected components) and spectral sparsification. Specifically, we present two methods, spectral vertex sampling $$BC\_SV$$ B C _ S V and spectral edge sampling $$BC\_SS$$ B C _ S S by computing effective resistance values of vertices and edges for each connected component. Furthermore, we present $$DBC\_SS$$ D B C _ S S and $$DBC\_GD$$ D B C _ G D , graph connectivity-based distributed algorithms for spectral sparsification and graph drawing respectively, aiming to further improve the runtime efficiency of spectral sparsification and graph drawing by integrating connectivity-based graph decomposition and distributed computing. Experimental results demonstrate that $$BC\_SV$$ B C _ S V and $$BC\_SS$$ B C _ S S are significantly faster than previous spectral graph sampling methods while preserving the same sampling quality. $$DBC\_SS$$ D B C _ S S and $$DBC\_GD$$ D B C _ G D obtain further significant runtime improvement over sequential approaches, and $$DBC\_GD$$ D B C _ G D further achieves significant improvements in quality metrics over sequential graph drawing layouts. 

   more » « less
5. Fluctuations of subgraph counts in graphon based random graphs

   https://doi.org/10.1017/S0963548322000335  

   Bhattacharya, Bhaswar B. ; Chatterjee, Anirban ; Janson, Svante ( May 2023 , Combinatorics, Probability and Computing)

   Abstract Given a graphon $W$ and a finite simple graph $H$ , with vertex set $V(H)$ , denote by $X_n(H, W)$ the number of copies of $H$ in a $W$ -random graph on $n$ vertices. The asymptotic distribution of $X_n(H, W)$ was recently obtained by Hladký, Pelekis, and Šileikis [17] in the case where $H$ is a clique. In this paper, we extend this result to any fixed graph $H$ . Towards this we introduce a notion of $H$ -regularity of graphons and show that if the graphon $W$ is not $H$ -regular, then $X_n(H, W)$ has Gaussian fluctuations with scaling $n^{|V(H)|-\frac{1}{2}}$ . On the other hand, if $W$ is $H$ -regular, then the fluctuations are of order $n^{|V(H)|-1}$ and the limiting distribution of $X_n(H, W)$ can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centred chi-squared random variables with the weights determined by the spectral properties of a graphon derived from $W$ . Our proofs use the asymptotic theory of generalised $U$ -statistics developed by Janson and Nowicki [22]. We also investigate the structure of $H$ -regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also $H$ -regular graphons $W$ for which both the Gaussian or the non-Gaussian components are degenerate, that is, $X_n(H, W)$ has a degenerate limit even under the scaling $n^{|V(H)|-1}$ . We give an example of this degeneracy with $H=K_{1, 3}$ (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher order degeneracies. 

   more » « less