Search

Influence maximization (IM) seeks to identify a seed set that maximizes influence within a network, with applications in areas such as viral marketing, disease control, and political campaigns. The budgeted influence maximization (BIM) problem extends IM by incorporating cost constraints for different nodes. However, the current BIM problem, limited by budget alone, often results in the selection of numerous low-cost nodes, which may not be applicable to real-world scenarios. Moreover, considering that users can transmit information across multiple social platforms, solving the BIM problem across these platforms could lead to more optimized resource utilization. To address these challenges, we propose the Budget and Capacity Constrained Influence Maximization (BCIM) problem within multilayer networks and introduce a Multilayer Multi-population Genetic Algorithm (MMGA) to solve it. The MMGA employs modules, such as initialization, repair, and parallel evolution, designed not only to meet budget and capacity constraints but also to significantly enhance algorithmic efficiency. Extensive experiments on both synthetic and empirical multilayer networks demonstrate that MMGA improves spreading performance by at least 10% under the two constraints compared to baselines extended from classical IM problems. The BCIM framework introduces a novel direction in influence maximization, providing an effective and efficient solution to the problem.

A social interaction (so-called higher-order event/interaction) can be regarded as the activation of the hyperlink among the corresponding individuals. Social interactions can be, thus, represented as higher-order temporal networks, that record the higher-order events occurring at each time step over time. The prediction of higher-order interactions is usually overlooked in traditional temporal network prediction methods, where a higher-order interaction is regarded as a set of pairwise interactions. The prediction of future higher-order interactions is crucial to forecast and mitigate the spread the information, epidemics and opinion on higher-order social contact networks. In this paper, we propose novel memory-based models for higher-order temporal network prediction. By using these models, we aim to predict the higher-order temporal network one time step ahead, based on the network observed in the past. Importantly, we also intent to understand what network properties and which types of previous interactions enable the prediction. The design and performance analysis of these models are supported by our analysis of the memory property of networks, e.g., similarity of the network and activity of a hyperlink over time respectively. Our models assume that a target hyperlink's future activity (active or not) depends the past activity of the target link and of all or selected types of hyperlinks that overlap with the target. We then compare the performance of both models with a baseline utilizing a pairwise temporal network prediction method. In eight real-world networks, we find that both models consistently outperform the baseline and the refined model tends to perform the best. Our models also reveal how past interactions of the target hyperlink and different types of hyperlinks that overlap with the target contribute to the prediction of the target's future activity., Comment: arXiv admin note: text overlap with arXiv:2309.04376

C/2019 Y4 (ATLAS) is an Oort cloud comet with an orbital period of $\sim$5895$\,{\rm yr}$. Starting in March 2020, its nucleus underwent disintegration. In order to investigate the gas and dust properties of C/2019 Y4 (ATLAS) during its disintegration, we obtained long-slit spectra at 3600--8700$\,{\rm\mathring{A}}$ and $BVRI$ multi-band images with the Xinglong 2.16-Meter Telescope in April 2020. Our observations revealed that C/2019 Y4 (ATLAS) exhibited strong emission bands of CN, C$_2$, C$_3$, and NH$_2$ which are superimposed on a dust scattering continuum, typical of cometary spectra in the optical. The production rates of CN, C$_2$, and C$_3$ derived using the Haser model and the corresponding C$_2$/CN and C$_3$/CN ratios suggest that C/2019 Y4 (ATLAS) is a ``typical'' Oort cloud comet under the A'Hearn classification, although it appears less dusty as revealed by the $Af\rho$ quantities. Its dust-scattering reflectivity is slightly red, with a gradient of $\sim$5% per $10^3\,{\rm\mathring{A}}$. We model the reflectivity gradient in terms of porous dust and find that the red color is accounted for by porous dust., Comment: 18 pages, 8 figures, 4 tables, accepted for publication in ApJ

Nodal spreading influence is the capability of a node to activate the rest of the network when it is the seed of spreading. Combining nodal properties (centrality metrics) derived from local and global topological information respectively is shown to better predict nodal influence than a single metric. In this work, we investigate to what extent local and global topological information around a node contributes to the prediction of nodal influence and whether relatively local information is sufficient for the prediction. We show that by leveraging the iterative process used to derives a classical nodal centrality such as eigenvector centrality, we can define an iterative metric set that progressively incorporates more global information around the node. We propose to predict nodal influence using an iterative metric set that consists of an iterative metric from order $1$ to $K$ that are produced in an iterative process, encoding gradually more global information as $K$ increases. Three iterative metrics are considered, which converge to three classical node centrality metrics respectively. Our results show that for each of the three iterative metrics, the prediction quality is close to optimal when the metric of relatively low orders ($K\sim4$) are included and increases only marginally when further increasing $K$. The best performing iterative metric set shows comparable prediction quality to the benchmark that combines seven centrality metrics, in both real-world networks and synthetic networks with community structures. Our findings are further explained via the correlation between an iterative metric and nodal influence, the convergence of iterative metrics and network properties.

A social interaction (so-called higher-order event/interaction) can be regarded as the activation of the hyperlink among the corresponding individuals. Social interactions can be, thus, represented as higher-order temporal networks, that record the higher-order events occurring at each time step over time. The prediction of higher-order interactions is usually overlooked in traditional temporal network prediction methods, where a higher-order interaction is regarded as a set of pairwise interactions. We propose a memory-based model that predicts the higher-order temporal network (or events) one step ahead, based on the network observed in the past and a baseline utilizing pair-wise temporal network prediction method. In eight real-world networks, we find that our model consistently outperforms the baseline. Importantly, our model reveals how past interactions of the target hyperlink and different types of hyperlinks that overlap with the target hyperlinks contribute to the prediction of the activation of the target link in the future., Comment: Submitted to the Conference on Complex Networks and Their Applications XII

Type II supernovae represent the most common stellar explosions in the Universe, for which the final stage evolution of their hydrogen-rich massive progenitors towards core-collapse explosion are elusive. The recent explosion of SN 2023ixf in a very nearby galaxy, Messier 101, provides a rare opportunity to explore this longstanding issue. With the timely high-cadence flash spectra taken within 1-5 days after the explosion, we can put stringent constraints on the properties of the surrounding circumstellar material around this supernova. Based on the rapid fading of the narrow emission lines and luminosity/profile of $\rm H\alpha$ emission at very early times, we estimate that the progenitor of SN 2023ixf lost material at a mass-loss rate $\dot{\rm M} \approx 6 \times 10^{-4}\, \rm M_{\odot}\,a^{-1}$ over the last 2-3 years before explosion. This close-by material, moving at a velocity $v_{\rm w} \approx 55\rm \, km\,s^{-1}$, accumulates a compact CSM shell at the radius smaller than $7 \times 10^{14}$ cm from the progenitor. Given the high mass-loss rate and relatively large wind velocity presented here, together with the pre-explosion observations made about two decades ago, the progenitor of SN 2023ixf could be a short-lived yellow hypergiant that evolved from a red supergiant shortly before the explosion., Comment: 10 pages, 6 figures in main body, Science Bulletin (Available online 14 September 2023)

A major challenge in synthetic genetic circuit development is the inter-dependency between heterologous gene expressions by circuits and host's growth rate. Increasing heterologous gene expression increases burden to the host, resulting in host growth reduction; which reduces overall heterologous protein abundance. Hence, it is difficult to design predictable genetic circuits. Here, we develop two biophysical models; one for promoter, another for RBS; to correlate heterologous gene expression and growth reduction. We model cellular resource allocation in E. coli to describe the burden, as growth reduction, caused by genetic circuits. To facilitate their uses in genetic circuit design, inputs to the model are common characteristics of biological parts [e.g. relative promoter strength (RPU) and relative ribosome binding sites strength (RRU)]. The models suggest that E. coli's growth rate reduces linearly with increasing RPU / RRU of the genetic circuits; thus, providing 2 handy models taking parts characteristics as input to estimate growth rate reduction for fine tuning genetic circuit design in silico prior to construction. Our promoter model correlates well with experiments using various genetic circuits, both single and double expression cassettes, up to a relative promoter unit of 3.7 with a 60% growth rate reduction (average R2 ~ 0.9).

Human social interactions are typically recorded as time-specific dyadic interactions, and represented as evolving (temporal) networks, where links are activated/deactivated over time. However, individuals can interact in groups of more than two people. Such group interactions can be represented as higher-order events of an evolving network. Here, we propose methods to characterize the temporal-topological properties of higher-order events to compare networks and identify their (dis)similarities. We analyzed 8 real-world physical contact networks, finding the following: a) Events of different orders close in time tend to be also close in topology; b) Nodes participating in many different groups (events) of a given order tend to involve in many different groups (events) of another order; Thus, individuals tend to be consistently active or inactive in events across orders; c) Local events that are close in topology are correlated in time, supporting observation a). Differently, in 5 collaboration networks, observation a) is almost absent; Consistently, no evident temporal correlation of local events has been observed in collaboration networks. Such differences between the two classes of networks may be explained by the fact that physical contacts are proximity based, in contrast to collaboration networks. Our methods may facilitate the investigation of how properties of higher-order events affect dynamic processes unfolding on them and possibly inspire the development of more refined models of higher-order time-varying networks.

Large pre-trained neural networks are ubiquitous and critical to the success of many downstream tasks in natural language processing and computer vision. However, within the field of web information retrieval, there is a stark contrast in the lack of similarly flexible and powerful pre-trained models that can properly parse webpages. Consequently, we believe that common machine learning tasks like content extraction and information mining from webpages have low-hanging gains that yet remain untapped. We aim to close the gap by introducing an agnostic deep graph neural network feature extractor that can ingest webpage structures, pre-train self-supervised on massive unlabeled data, and fine-tune to arbitrary tasks on webpages effectually. Finally, we show that our pre-trained model achieves state-of-the-art results using multiple datasets on two very different benchmarks: webpage boilerplate removal and genre classification, thus lending support to its potential application in diverse downstream tasks., Comment: Submitted to CIKM '22

Relational graph neural networks have garnered particular attention to encode graph context in knowledge graphs (KGs). Although they achieved competitive performance on small KGs, how to efficiently and effectively utilize graph context for large KGs remains an open problem. To this end, we propose the Relation-based Embedding Propagation (REP) method. It is a post-processing technique to adapt pre-trained KG embeddings with graph context. As relations in KGs are directional, we model the incoming head context and the outgoing tail context separately. Accordingly, we design relational context functions with no external parameters. Besides, we use averaging to aggregate context information, making REP more computation-efficient. We theoretically prove that such designs can avoid information distortion during propagation. Extensive experiments also demonstrate that REP has significant scalability while improving or maintaining prediction quality. Notably, it averagely brings about 10% relative improvement to triplet-based embedding methods on OGBL-WikiKG2 and takes 5%-83% time to achieve comparable results as the state-of-the-art GC-OTE., Comment: Accepted by IJCAI 2022

Many real-world complex systems including human interactions can be represented by temporal (or evolving) networks, where links activate or deactivate over time. Characterizing temporal networks is crucial to compare such systems and to study the dynamical processes unfolding on them. A systematic method to characterize simultaneously the temporal and topological relations of active links (also called contacts or events), in order to compare different real-world networks and to detect their common patterns or differences is still missing. In this paper, we propose a method to characterize to what extent contacts that happen close in time occur also close in topology. Specifically, we study the interrelation between temporal and topological properties of contacts from three perspectives: (1) the autocorrelation of the time series recording the total number of contacts happened at each time step in a network; (2) the interplay between the topological distance and interevent time of two contacts; (3) the temporal correlation of contacts within local neighborhoods beyond a node pair. By applying our method on 13 real-world temporal networks, we found that temporal-topological correlation of contacts is more evident in virtual contact networks than in physical contact ones. This could be due to the lower cost and easier access of online communications than physical interactions, allowing and possibly facilitating social contagion, i.e., interactions of one individual may influence the activity of its neighbors. We also identify different patterns between virtual and physical networks and among physical contact networks at, e.g., school and workplace, in the formation of correlation in local neighborhoods. Detected patterns and differences may further inspire the development of more realistic temporal network models, that could reproduce jointly temporal and topological properties of contacts., Comment: Manuscript accepted by Journal of Complex Networks