Non-fungible tokens (NFTs) have emerged as a transformative innovation in art and technology, relying heavily on social networks for promotion and revenue generation. The value of NFTs is profoundly influenced by their scarcity, rarity, and unique breeding mechanisms, which present novel challenges for viral marketing strategies. In this paper, we introduce a new research problem of NFT Revenue Maximization (NRM), which focuses on maximizing revenue from the perspective of NFT marketplaces by optimally selecting users for viral marketing campaigns (NFT airdrops) and determining the ideal quantities of NFTs to release. We prove the hardness of NRM and propose an approximation algorithm named Quantity and Offspring-Oriented Airdrops (QOOA). Our algorithm leverages the concepts of Scarcity-Conscious Revenue and Valuation-based Quantity Inequality to prune suboptimal airdrops and quantities at an early stage. To further enhance revenue through NFT breeding, QOOA identifies and incentivizes Rare Trait Collectors to acquire multiple NFTs with rare traits, facilitating the breeding of high-value offspring. Experimental results demonstrate that QOOA significantly outperforms baselines, achieving up to 3.8 times higher revenue in large-scale social networks.

The rapid development of multi-view videos (MVV) transmission is an irresistible trend. Concurrently, reconfigurable intelligent surface (RIS)-assisted wireless communication has drawn significant attention. We observe that the view selection based on the base station and the view synthesis based on depth-image-based rendering (DIBR) can effectively reduce power consumption. Therefore, this paper studies the view selection and synthesis for RIS-aided MVV in multigroup multicast beamforming. To deal with this complicated scenario, we investigate a problem, named the joint View selection, Multicast beamforming, and DIBR (JVMD), to minimize the total multicast beamforming power, the view transmission operation power, and view synthesis, subject to quality-of-service (QoS), RIS phase shifts, view selection, and DIBR constraints. Unfortunately, the mathematical model is a complicated mixed discrete-continuous optimization problem. To tackle this challenging problem, we designed an algorithm, named View selection, Beamforming, RIS phase, and DIBR (VBRD) algorithm. First, we deal with the discrete optimization problem of selecting the view. VBRD uses the dual-based approximation methodology to round back a primal's integer solution. Then, in the continuous optimization problem, we apply the alternating optimization (AO) method to determine beamforming, RIS phase, and DIBR. Finally, simulation results show the performance of exploiting view synthesis for RIS-assisted wireless communication.

New radio (NR) and non-orthogonal multiple access (NOMA) offer scalable and efficient resource allocation in Beyond 5G (B5G) networks. NR implements mixed numerology with flexible frame structures for future compatibility, whereas NOMA allows users with different channel states to share an identical Physical Resource Block (PRB). Multi-connectivity enables a user to connect to multiple networks for reliability, and multicast conveys data to users simultaneously that request the same content. However, resource allocation in the NOMA-based mixed numerology system with multi-connectivity for multicast remains unexplored. The problem is challenging due to 1) the different shapes of PRBs in NR and 2) the shared locations of PRBs in a frame with NOMA. In this paper, we formulate a new optimization problem, named Multicast, Multi-connectivity, and Multi-Dimensional Resource Allocation Problem (M3DRAP), and prove its NP-hardness and inapproximability. We propose an approximation algorithm for general M3DRAP with the ideas ofMulticast Inter-Numerology Relation,Layer Dissimilarity,Subgrouping Nonuniformity, andSegmentation Preference. To find the intrinsic properties of PRB allocation for multicast in NOMA-based networks, we consider a single B5G usage scenario (e.g., eMBB, URLLC, or mMTC) and propose another approximation algorithm. Simulations demonstrate our algorithms improve the weighted sum rate by over 50% and increase the user satisfaction ratio by 1.5x.

The emergence of AI has shifted the focus of wireless communications towards deep semantic-level fidelity (i.e., semantic communication networks), emphasizing the significance and effectiveness of transmitted data. However, semantic feature selection considering multicast users with social relations for feature sharing has not been explored. In this paper, we formulate a new optimization problem to minimize the total communication, forwarding, and computation costs, with the proof of NP-hardness and inapproximability. We propose a new algorithm, Multicast Semantic Feature Selection (MSFS), with the notions of Cross Task Semantic Indicator, Substituted Subgraph, and Socially Feature Selection Indicator, to select features on different mobile edge computing servers and cluster the users to receive features via multicast. Simulations with real datasets manifest that MSFS can reduce the total cost by more than 50% compared with state-of-the-art algorithms.

Recent pandemics, such as H1N1 and COVID-19, have had extensive negative effects on the social and economic well-being of communities. Despite efforts to prevent and control their spread, governments have turned to a strategy of Living With the Virus to manage, rather than eliminate, the impact of these pandemics. However, group activities such as collaborative spatial crowdsourcing can still lead to the significant spread of infection due to the correlation between individuals’ mobility, interactions, and infection spread. In this paper, we address the problem of spatial crowdsourcing-induced infection spread and propose Epidemic-aware Maximum Task Assignment (EMTA). EMTA aims to form and assign collaborative worker groups to spatial crowdsourcing tasks while taking into consideration the control of epidemic spread. We prove that EMTA is NP-hard and inapproximable. We then propose the Epidemic-aware Task Assignment Algorithm (ETAA) that leverages epidemic characteristics to fully address EMTA. The experimental results from real LBSN and real epidemic datasets demonstrate that the proposed algorithm outperforms the state-of-the-art baselines in terms of effectiveness and efficiency.

3GPP has defined Dual Connectivity (DC) to allow a user to access a 4G and a 5G base station (BS) simultaneously. However, the resource allocation for DC is challenging because of not only the co-channel interference between 4G and 5G BSs but also different shapes of Resource Blocks (RBs) for New Radio (NR) and the reuse of RBs for Non-Orthogonal Multiple Access (NOMA). In this paper, we formulate Dual Connectivity Multidimensional Resource Allocation Problem and prove that it is NP-hard. We design an approximation algorithm with the ideas of 1) Zone Shaping, 2) Occupancy Indicator and Overlap Degree of RBs, 3) DC Slicing, and 4) DC Inter-Numerology Relation, to maximize the total throughput of heterogeneous user demands in the coexisting 4G and 5G network with NR, NOMA, and DC. Simulation results manifest that our algorithm outperforms the state-of-the-arts regarding throughput and resource efficiency.

With the advances in Social Internet of Things (SIoT) and Federated learning (FL), smart devices are now able to cooperatively and locally perform learning tasks to protect sensitive data by Differential Privacy (DP). On the other hand, Hierarchical FL (HFL) clusters SIoTs into multiple local training groups to reduce communication overheads by local aggregation. In this paper, we explore SIoT Training Group Construction (STGC) for HFL to minimize the total SIoT computation, communication and hiring costs, and the privacy cost for exploiting DP. We prove that STGC is NP-hard and inapproximable within any factor unless P = NP. Then, we design an algorithm with the ideas of Coverage Efficiency Indicator, Data Balance-aware Dual Adjustment, and Privacy-Aware Rerouting to choose and cluster SIoTs and to determine the aggregator for local training and SIoT routing in each cluster. Simulation results manifest that the proposed algorithm outperforms state-of-the-arts regarding the total cost, model accuracy, and convergence time.

Epidemics such as COVID-19, SARS, H1N1 have highly transmissible viruses and spread wildly through the population with negative consequences. Multiple studies have shown the correlation between the contact networks between individuals and the transmission of infections due to contact between colocated individuals. To mitigate the transmission of the virus, intervention measures have been applied without decisive success. Therefore, reducing transmissions through suitable epidemicaware POI recommendations to users is necessary to cope with user mobility. Current POI recommendation approaches do not take into consideration the transmission of infections between co-located users. In this paper, we formulate a new query named Epidemic-aware POI Recommendation Query (EPQ), to timely recommend a set of POIs to users at different time steps, while considering the spread of infection between co-located users, their social friendships, and their preference. We prove that EPQ is NP-hard and propose an effective and efficient algorithm, Epidemic-aware POI Recommendation (EpRec) to tackle EPQ. We evaluate EpRec on existing location-based social networks and pandemic datasets against state-of-the-art algorithms. The experimental results show that EpRec outperforms the baselines in effectiveness and efficiency.

Research on new queries for finding dense subgraphs and groups has been actively pursued due to their many applications, especially in social network analysis and graph mining. However, existing work faces two major weaknesses: i) incapability of supporting personalized neighborhood density, and ii) inability to find sparse groups. To tackle the above issues, we propose a new query, called Density-Customized Social Group Query (DCSGQ), that accommodates the need for personalized density by allowing individual users to flexibly configure their social tightness (and sparseness) for the target group. The proposed DCSGQ is general due to flexible in configuration of neighboring social density in queries. We prove the NP-hardness and inapproximability of DCSGQ, formulate an Integer Program (IP) as a baseline, and propose an efficient algorithm, FSGSel-RR, by relaxing the IP. We then propose a fixed-parameter tractable algorithm with a performance guarantee, named FSGSel-TD, and further combine it with FSGSel-RR into a hybrid approach, named FSGSel-Hybrid, in order to strike a good balance between solution quality and efficiency. Extensive experiments on multiple large real datasets demonstrate the superior solution quality and efficiency of our approaches over existing subgraph and group queries.

Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group with No-Pair Constraint (MkTG), to find a socially tenuous group from the online social network. We prove that MkTG is NP-hard and inapproximable within any ratio. Two algorithms, namely TERA and TERA-ADV, are designed for solving MkTG effectively and efficiently. Further, we examine the MkTG problem on tree-based social networks, due to their structural resemblance with corporate social networks built upon the supervision relation. Accordingly, we devise an efficient algorithm, namely Tenuity Maximization for Trees (TMT), to obtain the optimal solution in polynomial time. In addition, we study a more general version of MkTG, named Generalized Minimum k-Triangle Disconnected Group without No-Pair Constraint (MkTG-G). We formulate MkTG-G, analyze its inapproximability, and propose a randomized approximation algorithm, named Randomized Ranking with Limited Neighborhood Participation (RLNP). Experimental results on real datasets manifest that the proposed algorithms outperform the baselines in terms of both efficiency and solution quality.

New radio (NR) and non-orthogonal multiple access (NOMA) have emerged for more scalable and efficient resource utilization in 5G. NR implements mixed numerology with a flexible radio frame structure to ensure forward compatibility for future services, whereas NOMA allows multiple users with different channel states to share identical radio resources. However, the resource allocation in the NOMA-based mixed numerology system is challenging due to the naturally different shapes of Physical Resource Block (PRB) for NR and the reused locations of PRBs in a radio frame for NOMA. In this paper, we formulate a new optimization problem Multi-Dimensional Resource Allocation Problem (MDRAP) and prove that MDRAP is NP-hard. To solve the problem, we propose an approximation algorithm to maximize the weighted sum rate under the heterogeneity of users. The algorithm includes Zone Displacement to displace the locations of allocated PRBs in different layers of the radio frame, and Zone Allocation to change the location of the bounded rectangles (i.e., zones) for the allocation in each layer. We design Layer Dissimilarity to examine the location and shape of PRBs for avoiding inter-numerology interference between different layers. Simulation results show that the proposed algorithm outperforms state-of-the-art algorithms regarding throughput and fairness.

Many novel and exhilarating applications emerged in the past decade, thanks to the ubiquity and the volume of data in this big data era. However, large-scale data collection is often expensive and time-consuming, especially in the physical world. To address this issue, in this paper, we study a new research problem, named k-Collector Problem (k- CP), which considers to minimize the data collection time for a set of k data collectors in the road network. We propose a constant- ratio approximation algorithm, called Collective Search Walk Planning (CSP). Moreover, we also discuss different strategies to boost the efficiency of CSP. Experimental results on 3 real datasets show that our proposed CSP algorithm outperforms other baselines in both solution quality and efficiency.