Network connectivity minimization is a fundamental problem in controlling the spread of viruses in the Internet and facilitating information propagation in online social networks. The problem aims to identify a budget number of key nodes whose removal would minimize the connectivity of a network. However, the existing solutions heavily rely on the number of edges, making it challenging to handle large and densely connected social networks. In this study, we present a fast algorithm that is independent of the number of edges. To achieve this, we first introduce a surrogate matrix that approximates the residual adjacency matrix with arbitrary small predefined error. We then devise an efficient approach for inferring k influential nodes by optimizing the eigenvalues of the surrogate matrix. Remarkably, the algorithm has a small time complexity of O(knr3), with r being a small tunable number. Our algorithm thereby maintains a linear scalability in terms of the number of nodes and is unaffected by the number of edges. Hence, it has the capability to efficiently handle large and dense social networks. At last, we evaluate its performance against state-of-the-art techniques using diverse real-world datasets. The experimental results demonstrate the superiority of our proposed method in terms of both solution quality and computational efficiency.

Explainable recommender systems ( ERS ) aim to enhance users’ trust in the systems by offering personalized recommendations with transparent explanations. This transparency provides users with a clear understanding of the rationale behind the recommendations, fostering a sense of confidence and reliability in the system’s outputs. Generally, the explanations are presented in a familiar and intuitive way, which is in the form of natural language, thus enhancing their accessibility to users. Recently, there has been an increasing focus on leveraging reviews as a valuable source of rich information in both modeling user-item preferences and generating textual interpretations, which can be performed simultaneously in a multi-task framework. Despite the progress made in these review-based recommendation systems, the integration of implicit feedback derived from user-item interactions and user-written text reviews has yet to be fully explored. To fill this gap, we propose a model named SERMON (A s pect-enhanced E xplainable R ecommendation with M ulti-modal C o ntrast Lear n ing). Our model explores the application of multimodal contrastive learning to facilitate reciprocal learning across two modalities, thereby enhancing the modeling of user preferences. Moreover, our model incorporates the aspect information extracted from the review, which provides two significant enhancements to our tasks. Firstly, the quality of the generated explanations is improved by incorporating the aspect characteristics into the explanations generated by a pre-trained model with controlled textual generation ability. Secondly, the commonly used user-item interactions are transformed into user-item-aspect interactions, which we refer to as interaction triple, resulting in a more nuanced representation of user preference. To validate the effectiveness of our model, we conduct extensive experiments on three real-world datasets. The experimental results show that our model outperforms state-of-the-art baselines, with a 2.0% improvement in prediction accuracy and a substantial 24.5% enhancement in explanation quality for the TripAdvisor dataset.

Federated learning enables collaborative AI training across organizations without compromising data privacy. Decentralized federated learning (DFL) improves this by offering enhanced reliability and security through peer-to-peer (P2P) model sharing. However, DFL faces challenges in terms of slow convergence rate due to complex P2P graphs. To address this issue, we propose an efficient algorithm to accelerate DFL by introducing a limited number of k of edges into the P2P graphs. Specifically, we establish a connection between the convergence rate and the second smallest eigenvalue of the laplacian matrix of the P2P graph. We prove that finding the optimal set of edges to maximize this eigenvalue is an NP-complete problem. Our quantitative analysis shows the positive effect of strategic edge additions on improving this eigenvalue. Based on the analysis, we then propose an efficient algorithm to compute the best set of candidate edges to maximize the second smallest eigenvalue, and consequently the convergence rate is maximized. Our algorithm has a low time complexity of O(krn^2). Experimental results on diverse datasets validate the effectiveness of our proposed algorithms in accelerating DFL convergence.

In this paper, we present an algorithmic study on how to surpass competitors in popularity by strategic promotions in social networks. We first propose a novel model, in which we integrate the Preferential Attachment (PA) model for popularity growth with the Independent Cascade (IC) model for influence propagation in social networks called PA-IC model. In PA-IC, a popular item and a novice item grab shares of popularity from the natural popularity growth via the PA model, while the novice item tries to gain extra popularity via influence cascade in a social network. The popularity ratio is defined as the ratio of the popularity measure between the novice item and the popular item. We formulate Popularity Ratio Maximization (PRM) as the problem of selecting seeds in multiple rounds to maximize the popularity ratio in the end. We analyze the popularity ratio and show that it is monotone but not submodular. To provide an effective solution, we devise a surrogate objective function and show that empirically it is very close to the original objective function while theoretically, it is monotone and submodular. We design two efficient algorithms, one for the overlapping influence and non-overlapping seeds (across rounds) setting and the other for the non-overlapping influence and overlapping seed setting, and further discuss how to deal with other models and problem variants. Our empirical evaluation further demonstrates that our proposed method consistently achieves the best popularity promotion compared to other methods. Our theoretical and empirical analyses shed light on the interplay between influence maximization and preferential attachment in social networks.

Networks are one of the most powerful structures for modeling problems in the real world. Many machine learning algorithms, however, require that each input example is a real vector. Network embedding learns from feature representations of nodes and links in a network, and converts it to vectors. Community structure is an important feature of the network, which represents the relationship among nodes and attracts the attention of relevant researchers. Many algorithms have been developed to identify the community structure. These algorithms usually identify different communities in the network, generating different types of information. In this paper, we propose a "Community Splitter" model based on random walk and RNN (Recurrent Neural Networks) that combines the node information generated by multiple community detection algorithms to improve node representation and link prediction. Extensive experiments on nine real datasets demonstrate that our proposed Community Splitter model has a significant prediction power compared to state-of-the-art link prediction models.