Search

Top-k Nearest Neighbors (kNN) problem on road network has numerous applications on location-based services. As direct search using the Dijkstra's algorithm results in a large search space, a plethora of complex-index-based approaches have been proposed to speedup the query processing. However, even with the current state-of-the-art approach, long query processing delays persist, along with significant space overhead and prohibitively long indexing time. In this paper, we depart from the complex index designs prevalent in existing literature and propose a simple index named KNN-Index. With KNN-Index, we can answer a kNN query optimally and progressively with small and size-bounded index. To improve the index construction performance, we propose a bidirectional construction algorithm which can effectively share the common computation during the construction. Theoretical analysis and experimental results on real road networks demonstrate the superiority of KNN-Index over the state-of-the-art approach in query processing performance, index size, and index construction efficiency., Comment: 15 pages, 15 figures

Distributed processing of large-scale graph data has many practical applications and has been widely studied. In recent years, a lot of distributed graph processing frameworks and algorithms have been proposed. While many efforts have been devoted to analyzing these, with most analyzing them based on programming models, less research focuses on understanding their challenges in distributed environments. Applying graph tasks to distributed environments is not easy, often facing numerous challenges through our analysis, including parallelism, load balancing, communication overhead, and bandwidth. In this paper, we provide an extensive overview of the current state-of-the-art in this field by outlining the challenges and solutions of distributed graph algorithms. We first conduct a systematic analysis of the inherent challenges in distributed graph processing, followed by presenting an overview of existing general solutions. Subsequently, we survey the challenges highlighted in recent distributed graph processing papers and the strategies adopted to address them. Finally, we discuss the current research trends and identify potential future opportunities.

We determine the maximum number of a graph without containing the 2-power of a Hamilton path. Using this result, we establish a spectral condition for a graph containing the 2-power of a Hamilton path.

Hop-constrained s-t simple path (HC-s-t path) enumeration is a fundamental problem in graph analysis. Existing solutions for this problem focus on optimizing the processing performance of a single query. However, in practice, it is more often that multiple HC-s-t path queries are issued simultaneously and processed as a batch. Therefore, we study the problem of batch HC-s-t path query processing in this paper and aim to compute the results of all queries concurrently and efficiently as a batch. To achieve this goal, we first propose the concept of HC-s path query which can precisely characterize the common computation among different queries.We then devise a two-phase HC-s path query detection algorithm to identify the common HC-s path queries for the given HC-s-t path queries. Based on the detected HC-s path queries, we further devise an efficient HC-s-t path enumeration algorithm in which the common computation represented by HC-s path queries are effectively shared. We conduct extensive experiments on real-world graphs and the experimental results demonstrate that our proposed algorithm is efficient and scalable regarding processing multiple HC-s-t path queries in large graphs at billion-scale.

Structural clustering is one of the most popular graph clustering methods, which has achieved great performance improvement by utilizing GPUs. Even though, the state-of-the-art GPU-based structural clustering algorithm, GPUSCAN, still suffers from efficiency issues since lots of extra costs are introduced for parallelization. Moreover, GPUSCAN assumes that the graph is resident in the GPU memory. However, the GPU memory capacity is limited currently while many real-world graphs are big and cannot fit in the GPU memory, which makes GPUSCAN unable to handle large graphs. Motivated by this, we present a new GPU-based structural clustering algorithm, GPUSCAN++, in this paper. To address the efficiency issue, we propose a new progressive clustering method tailored for GPUs that not only avoid high parallelization costs but also fully exploits the computing resources of GPUs. To address the GPU memory limitation issue, we propose a partition-based algorithm for structural clustering that can process large graphs with limited GPU memory. We conduct experiments on real graphs, and the experimental results demonstrate that our algorithm can achieve up to 168 times speedup compared with the state-of-the-art GPU-based algorithm when the graph can be resident in the GPU memory. Moreover, our algorithm is scalable to handle large graphs. As an example, our algorithm can finish the structural clustering on a graph with 1.8 billion edges using less than 2 GB GPU memory.

In this paper we propose a {\it discontinuous} plane wave neural network (DPWNN) method with $hp-$refinement for approximately solving Helmholtz equation and time-harmonic Maxwell equations. In this method, we define a quadratic functional as in the plane wave least square (PWLS) method with $h-$refinement and introduce new discretization sets spanned by element-wise neural network functions with a single hidden layer, where the activation function on each element is chosen as a complex-valued exponential function like the plane wave function. The desired approximate solution is recursively generated by iteratively solving the minimization problem associated with the functional and the sets described above, which is defined by a sequence of approximate minimizers of the underlying residual functionals, where plane wave direction angles and activation coefficients are alternatively computed by iterative algorithms. For the proposed DPWNN method, the plane wave directions are adaptively determined in the iterative process, which is different from that in the standard PWLS method (where the plane wave directions are preliminarily given). Numerical experiments will confirm that this DPWNN method can generate approximate solutions with higher accuracy than the PWLS method.

The supersaturation problem for a given graph $F$ asks for the minimum number $h_F(n,q)$ of copies of $F$ in an $n$-vertex graph with $ex(n,F)+q$ edges. Subsequent works by Rademacher, Erd\H{o}s, and Lov\'{a}sz and Simonovits determine the optimal range of $q$ (which is linear in $n$) for cliques $F$ such that $h_F(n,q)$ equals the minimum number $t_F(n,q)$ of copies of $F$ obtained from a maximum $F$-free $n$-vertex graph by adding $q$ new edges. A breakthrough result of Mubayi extends this line of research from cliques to color-critical graphs $F$, and this was further strengthened by Pikhurko and Yilma who established the equality $h_F(n,q)=t_F(n,q)$ for $1\leq q\leq \epsilon_F n$ and sufficiently large $n$. In this paper, we present several results on the supersaturation problem that extend beyond the existing framework. Firstly, we explicitly construct infinitely many graphs $F$ with restricted properties for which $h_F(n,q)

Controlled charge flows are fundamental to many areas of science and technology, serving as carriers of energy and information, as probes of material properties and dynamics, and as a means of revealing or even inducing broken symmetries. Emerging methods for light-based current control offer promising routes beyond the speed and adaptability limitations of conventional voltage-driven systems. However, optical generation and manipulation of currents at nanometer spatial scales remains a basic challenge and a crucial step towards scalable optoelectronic systems for microelectronics and information science. Here, we introduce vectorial optoelectronic metasurfaces in which ultrafast light pulses induce local directional charge flows around symmetry-broken plasmonic nanostructures, with tunable responses and arbitrary patterning down to sub-diffractive nanometer scales. Local symmetries and vectorial current distributions are revealed by polarization- and wavelength-sensitive electrical readout and terahertz (THz) emission, while spatially-tailored global currents are demonstrated in the direct generation of elusive broadband THz vector beams. We show that in graphene, a detailed interplay between electrodynamic, thermodynamic, and hydrodynamic degrees of freedom gives rise to rapidly-evolving nanoscale driving forces and charge flows under extreme temporal and spatial confinement. These results set the stage for versatile patterning and optical control over nanoscale currents in materials diagnostics, THz spectroscopies, nano-magnetism, and ultrafast information processing.

Community search over bipartite graphs has attracted significant interest recently. In many applications such as user-item bipartite graph in E-commerce, customer-movie bipartite graph in movie rating website, nodes tend to have attributes, while previous community search algorithm on bipartite graphs ignore attributes, which makes the returned results with poor cohesion with respect to their node attributes. In this paper, we study the community search problem on attributed bipartite graphs. Given a query vertex q, we aim to find attributed $\left(\alpha,\beta\right)$-communities of $G$, where the structure cohesiveness of the community is described by an $\left(\alpha,\beta\right)$-core model, and the attribute similarity of two groups of nodes in the subgraph is maximized. In order to retrieve attributed communities from bipartite graphs, we first propose a basic algorithm composed of two steps: the generation and verification of candidate keyword sets, and then two improved query algorithms Inc and Dec are proposed. Inc is proposed considering the anti-monotonity property of attributed bipartite graphs, then we adopt different generating method and verifying order of candidate keyword sets and propose the Dec algorithm. After evaluating our solutions on eight large graphs, the experimental results demonstrate that our methods are effective and efficient in querying the attributed communities on bipartite graphs.

For a nondegenerate $r$-graph $F$, large $n$, and $t$ in the regime $[0, c_{F} n]$, where $c_F>0$ is a constant depending only on $F$, we present a general approach for determining the maximum number of edges in an $n$-vertex $r$-graph that does not contain $t+1$ vertex-disjoint copies of $F$. In fact, our method results in a rainbow version of the above result and includes a characterization of the extremal constructions. Our approach applies to many well-studied hypergraphs (including graphs) such as the edge-critical graphs, the Fano plane, the generalized triangles, hypergraph expansions, the expanded triangles, and hypergraph books. Our results extend old results of Simonovits~\cite{SI68} and Moon~\cite{Moon68} on complete graphs and can be viewed as a step towards a general density version of the classical Corr\'{a}di--Hajnal Theorem~\cite{CH63}., Comment: corrected some typo and added a theorem (THM 2.7) about expanded Erdos-Sos trees

One-dimensional (1D) organic metal halide hybrids exhibit strongly anisotropic optical properties, highly efficient light emission, and large Stokes shift, holding promises for novel photodetection and lighting applications. However, the fundamental mechanisms governing their unique optical properties and in particular the impacts of surface effects are not understood. Here, we investigate 1D C4N2H14PbBr4 by polarization-dependent time-averaged and time-resolved photoluminescence (TRPL) spectroscopy, as a function of photoexcitation energy. Surprisingly, we find that the emission under photoexcitation polarized parallel to the 1D metal halide chains can be either stronger or weaker than that under perpendicular polarization, depending on the excitation energy. We attribute the excitation-energy-dependent anisotropic emission to fast surface recombination, supported by first-principles calculations of optical absorption in this material. The fast surface recombination is directly confirmed by TRPL measurements, when the excitation is polarized parallel to the chains. Our comprehensive studies provide a more complete picture for a deeper understanding of the optical anisotropy in 1D organic metal halide hybrids.

The search for the experimental evidence of quantum spin liquid (QSL) states is critical but extremely challenging, as the quenched interaction randomness introduced by structural imperfection is usually inevitable in real materials. YCu$_3$(OH)$_{6.5}$Br$_{2.5}$ (YCOB) is a spin-1/2 kagome Heisenberg antiferromagnet (KHA) with strong coupling of $\langle J_1\rangle\sim$ 51 K but without conventional magnetic freezing down to 50 mK $\sim$ 0.001$\langle J_1\rangle$. Here, we report a Br nuclear magnetic resonance (NMR) study of the local spin susceptibility and dynamics on the single crystal of YCOB. The temperature dependence of NMR main-line shifts and broadening can be well understood within the frame of the KHA model with randomly distributed hexagons of alternate exchanges, compatible with the formation of a randomness-induced QSL state at low temperatures. The in-plane spin fluctuations as measured by the spin-lattice relaxation rates ($1/T_1$) exhibit a weak temperature dependence down to $T$ $\sim$ 0.03$\langle J_1\rangle$. Our results demonstrate that the majority of spins remain highly fluctuating at low temperatures despite the quenched disorder in YCOB., Comment: NMR work on YCu3(OH)6.5Br2.5, accepted in Communications Physics

The Erd\H{o}s-Simonovits stability theorem is one of the most widely used theorems in extremal graph theory. We obtain an Erd\H{o}s-Simonovits type stability theorem in multi-partite graphs. Different from the Erd\H{o}s-Simonovits stability theorem, our stability theorem in multi-partite graphs says that if the number of edges of an $H$-free graph $G$ is close to the extremal graphs for $H$, then $G$ has a well-defined structure but may be far away to the extremal graphs for $H$. As an application, we solve a conjecture posed by Han and Zhao concerning the maximum number of edges in multi-partite graphs which does not contain vertex-disjoint copies of a clique

We show that short-range resonating-valence-bond correlations and long-range order can coexist in the ground state (GS) of a frustrated spin system. Our study comprises a comprehensive investigation of the quantum magnetism on the structurally disorder-free single crystal of Cu$_2$(OH)$_3$NO$_3$, which realizes the $s$ = 1/2 Heisenberg model on a spatially anisotropic triangular lattice. Competing exchange interactions determined by fitting the magnetization measured up to 55 T give rise to an exotic GS wavefunction with coexistence of the dominant short-range resonating-valence-bond correlations and weak long-range stripe order (ordered moment $M_0$ = $|\langle s_i^z\rangle|$ $\sim$ 0.02). At low temperatures, a first-order spin-flop transition is visible at $\sim$ 1-3 T. As the applied field further increases, another two magnetic-field-induced quantum phase transitions are observed at $\sim$ 14-19 and $\sim$ 46-52 T, respectively. Simulations of the Heisenberg exchange model show semi-quantitative agreement with the magnetic-field modulation of these unconventional phases, as well as the absence of visible magnetic reflections in neutron diffraction, thus supporting the GS of the spin system of Cu$_2$(OH)$_3$NO$_3$ may be approximate to a quantum spin liquid. Our study establishes structurally disorder-free magnetic materials with spatially anisotropic exchange interactions as a possible arena for spin liquids., Comment: Accepted in PRB

In this paper, we study the stability result of a well-known theorem of Bondy. We prove that for any 2-connected non-hamiltonian graph, if every vertex except for at most one vertex has degree at least $k$, then it contains a cycle of length at least $2k+2$ except for some special families of graphs. Our results imply several previous classical theorems including a deep and old result by Voss. We point out our result on stability in Bondy's theorem can directly imply a positive solution (in a slight stronger form) to the following problem: Is there a polynomial time algorithm to decide whether a 2-connected graph $G$ on $n$ vertices has a cycle of length at least $\min\{2\delta(G)+2,n\}$. This problem originally motivates the recent study on algorithmic aspects of Dirac's theorem by Fomin, Golovach, Sagunov and Simonov, although a stronger problem was solved by them by completely different methods. Our theorem can also help us to determine all extremal graphs for wheels on odd number of vertices. We also discuss the relationship between our results and some previous problems and theorems in spectral graph theory and generalized Tur\'{a}n problem., Comment: 17 pages

The edge blow-up of a graph is the graph obtained from replacing each edge of it by a clique of the same size where the new vertices of the cliques are all different. Wang, Hou, Liu and Ma determined the Tur\'{a}n number of the edge blow-up of trees except one particular case. Answering an problem posed by them, we determined the Tur\'{a}n number of this particular case.

The spin-1/2 kagom\'{e} Heisenberg antiferromagnet is generally accepted as one of the most promising two-dimensional models to realize a quantum spin liquid state. Previous experimental efforts were almost exclusively on only one archetypal material, the herbertsmithite ZnCu$_3$(OH)$_6$Cl$_2$, which unfortunately suffers from the notorious orphan spins problem caused by magnetic disorders. Here we turn to YCu$_3$(OH)$_{6.5}$Br$_{2.5}$, recently recognized as another host of a globally undistorted kagom\'{e} Cu$^{2+}$ lattice free from the orphan spins, thus a more feasible system for studying the intrinsic kagom\'{e} quantum spin liquid physics. Our high-resolution low-temperature thermal conductivity measurements yield a vanishing small residual linear term of $\kappa/T$ ($T\rightarrow 0$), and thus clearly rule out itinerant gapless fermionic excitations. Unusual scattering of phonons grows exponentially with temperature, suggesting thermally activated phonon-spin scattering and hence a gapped magnetic excitation, consistent with a $\mathbb{Z}_2$ quantum spin liquid ground state. Additionally, the analysis of magnetic field impact on the thermal conductivity reveals a field closing of the spin gap, while the excitations remain localized., Comment: 4 figures

Clique is one of the most fundamental models for cohesive subgraph mining in network analysis. Existing clique model mainly focuses on unsigned networks. However, in real world, many applications are modeled as signed networks with positive and negative edges. As the signed networks hold their own properties different from the unsigned networks, the existing clique model is inapplicable for the signed networks. Motivated by this, we propose the balanced clique model that considers the most fundamental and dominant theory, structural balance theory, for signed networks. Following the balanced clique model, we study the maximal balanced clique enumeration problem (MBCE) which computes all the maximal balanced cliques in a given signed network and the maximum balanced clique search problem (MBCS) which computes the balanced clique with maximum size. We show that MBCE problem and MBCS problem are both NP-Hard. For the MBCE problem, a straightforward solution is to treat the signed network as two unsigned networks and leverage the off-the-shelf techniques for unsigned networks. However, such a solution is inefficient for large signed networks. To address this problem, in this paper, we first propose a new maximal balanced clique enumeration algorithm by exploiting the unique properties of signed networks. Based on the new proposed algorithm, we devise two optimization strategies to further improve the efficiency of the enumeration. For the MBCS problem, we propose a new search framework based on search space partition. To further improve the efficiency of the new framework, we propose multiple optimization strategies regarding to redundant search branches and invalid candidates. We conduct extensive experiments on large real datasets. The experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms for MBCE problem and MBCS problem.

Recent advances in the growth of III-V semiconductor nanowires (NWs) hold great promise for nanoscale optoelectronic device applications. Recently, it was found that a small amount of nitrogen (N) incorporation in III-V semiconductor NWs can effectively red-shift their wavelength of operation and tailor their electronic properties for specific applications. However, understanding the impact of N incorporation on non-equilibrium charge carrier dynamics and transport in semiconducting NWs is critical in achieving efficient semiconducting NW devices. In this work, ultrafast optical pump-terahertz (THz) probe spectroscopy (OPTP) and electrical characterization have been used to study non-equilibrium carrier dynamics and equilibrium transport in Te-doped GaAsSb and dilute nitride GaAsSb NWs, with the goal of correlating these results with their photo-response under bias and their low-frequency noise characteristics. Nitrogen incorporation in GaAsSb NWs led to a significant increase in the carrier scattering rate, resulting in a severe reduction in carrier mobility. Carrier recombination lifetimes of 33 ps and 147 ps in GaAsSbN and GaAsSb NWs, respectively, were determined using ultrafast OPTP measurements. The reduction in the carrier lifetime and photoinduced optical conductivities are due to the presence of N-induced defects, leading to deterioration in the electrical and optical characteristics of dilute nitride NWs relative to the non-nitride NWs. Finally, we observed a very fast rise time of ~ 2 ps for both NW materials, directly impacting their potential use as high-speed photodetectors., Comment: One of co-author doesn't approve the submission

Motivated by the advancing computational capacity of distributed end-user equipments (UEs), as well as the increasing concerns about sharing private data, there has been considerable recent interest in machine learning (ML) and artificial intelligence (AI) that can be processed on on distributed UEs. Specifically, in this paradigm, parts of an ML process are outsourced to multiple distributed UEs, and then the processed ML information is aggregated on a certain level at a central server, which turns a centralized ML process into a distributed one, and brings about significant benefits. However, this new distributed ML paradigm raises new risks of privacy and security issues. In this paper, we provide a survey of the emerging security and privacy risks of distributed ML from a unique perspective of information exchange levels, which are defined according to the key steps of an ML process, i.e.: i) the level of preprocessed data, ii) the level of learning models, iii) the level of extracted knowledge and, iv) the level of intermediate results. We explore and analyze the potential of threats for each information exchange level based on an overview of the current state-of-the-art attack mechanisms, and then discuss the possible defense methods against such threats. Finally, we complete the survey by providing an outlook on the challenges and possible directions for future research in this critical area., Comment: arXiv admin note: text overlap with arXiv:1907.09470, arXiv:2003.02133, arXiv:1606.05053, arXiv:1812.06415 by other authors

The bipartite Tur\'{a}n number of a graph $H$, denoted by $ex(m,n; H)$, is the maximum number of edges in any bipartite graph $G=(X,Y; E)$ with $|X|=m$ and $|Y|=n$ which does not contain $H$ as a subgraph. In this paper, we determined $ex(m,n; F_{\ell})$ for arbitrary $\ell$ and appropriately large $n$ with comparing to $m$ and $\ell$, where $F_\ell$ is a linear forest which consists of $\ell$ vertex disjoint paths. Moreover, the extremal graphs have been characterized. Furthermore, these results are used to obtain the maximum spectral radius of bipartite graphs which does not contain $F_{\ell}$ as a subgraph and characterize all extremal graphs which attain the maximum spectral radius., Comment: 18 pages