In social networks, revealing the structure of communities can expose sensitive groups to detection. Traditional approaches, such as DICE, attempt to hide these communities by randomly rewiring links, but this strategy is often inefficient and insecure. We propose an efficient heuristic method called CRIME (Community Rewiring for Influence and Masking Entities) to address this challenge. CRIME removes the most influential internal links, measured by edge-betweenness centrality, and adds external links with the least betweenness centrality. Experiments on real-world networks demonstrate that CRIME hides targeted communities more effectively than DICE, and also achieves faster execution and improves hiding effectiveness by up to 99.8%.

On social media, it is easy to see how people are connected and find the leader, or mastermind of a network. The mastermind is responsible for the planning of the activities in the network. Hiding the mastermind is important to carry out these activities. This raises the question for the mastermind: How effectively can the mastermind hide his connections to avoid being found? We propose an efficient heuristic algorithm called HERMES (Hide Exposures by Removing Mastermind’s External Sources) to address this. Experiments on Facebook and Google networks show that HERMES hides the mastermind more effectively than the state-of-the-art, achieving time gains of 103 and 1397 seconds, respectively, and improving influence value by up to 11.11%.

Simultaneous Coalition Structure Generation and Assignment (SCSGA) is an important research problem in multi-agent systems. Given n agents and m tasks, the aim of SCSGA is to form m disjoint coalitions of n agents such that between the coalitions and tasks there is a one-to-one mapping, which ensures each coalition is capable of accomplishing the assigned task. SCSGA with Multi-dimensional Features (SCSGA-MF) extends the problem by introducing a d-dimensional vector for each agent and task. We propose a heuristic algorithm called Multiple Distance Metric (MDM) approach to solve SCSGA-MF. Experimental results confirm that MDM produces near optimal solutions, while being feasible for large-scale inputs within a reasonable time frame.

The growth of COVID-19, caused by the SARS-CoV-2 virus, has turned into an unprecedented pandemic in the last century. It is crucial to identify superspreading nodes to prevent the pandemic’s progress. Most available superspreader identification techniques consider only a single or few network metrics related to the complex network’s topological structure. Furthermore, it is more challenging to determine influential spreaders from heterogeneous structures of networks. In a disease transmission network, the degree of heterogeneity is essential to locate the path of the infection spread. Therefore, it is required to have an extended degree of centrality to collect information from various neighborhood levels. This article presents an approach, namely, global structure influence (GSI), which considers network nodes’ local and global influence. This method can gather information from multiple levels of the neighborhood. Evaluation of our proposed method is done by considering different types of networks, i.e., social networks, highly heterogeneous human contact networks, and epidemiological networks, and also by using the benchmark susceptible-infected-recovered (SIR) epidemic model. The GSI technique provides real-spreading dynamics across various network structures and has outperformed the baseline techniques with an average Kendall’s$\tau $improvement range from 0.017 to 0.278. This study will help to identify the superspeaders in real applications, where pathogens spread quickly because of close contact, such as the recently witnessed COVID-19 pandemic.

Abstract The objective of coalition formation is to partition the agent set that gives the highest utility to the system. Over the past three decades, the process of coalition formation has been applied to various real‐life applications where agents need to form efficient groups to accomplish a task. This article presents a study of the state‐of‐the‐art approaches on the applications of coalition formation. In particular, it surveys the algorithmic approaches for optimizing the system's welfare. The algorithms are then analyzed based on a framework that consists of two dimensions: (i) the features of the problem environment, which gives an overview of the complexity level of the environment, and (ii) the features of the problem solver, which gives an overview of the solution quality. Our study analyses the approaches in terms of the framework mentioned above, justifies the use of the approaches in a particular problem setting, presents guidance to choose the right algorithmic approach for a problem at hand, and classifies the state‐of‐the‐art approaches according to their basic working principles. This article also presents possible future directions of work to the research community. This study shows that theoretical models need more research before they can be deployed in the real world.

In this paper, we focus on the Coalition Structure Generation (CSG) problem, which involves finding exhaustive and disjoint partitions of agents such that the efficiency of the entire system is optimized. We propose an efficient hybrid algorithm for optimal coalition structure generation called BOSS. When compared to the state-of-the-art, BOSS is shown to perform better by up to 33.63% on benchmark inputs. The maximum time gain by BOSS is 3392 seconds for 27 agents.

Coalition Structure Generation (CSG) is an NP-complete problem that remains difficult to solve on account of its complexity. In this paper, we propose an efficient hybrid algorithm for optimal coalition structure generation called ODSS. ODSS is a hybrid version of two previously established algorithms IDP (Rahwan and Jennings 2008) and IP (Rahwan et al. 2009). ODSS minimizes the overlapping between IDP and IP by dividing the whole search space of CSG into two disjoint sets of subspaces and proposes a novel subspace shrinking technique to reduce the size of the subspace searched by IP with the help of IDP. When compared to the state-of-the-art against a wide variety of value distributions, ODSS is shown to perform better by up to 54.15% on benchmark inputs.

Optimal Coalition Structure Generation (CSG) is a significant research problem that remains difficult to solve. Given n agents, the ODP-IP algorithm (Michalak et al. 2016) achieves the current lowest worst-case time complexity of O(3n). We devise an Imperfect Dynamic Programming (ImDP) algorithm for CSG with runtime O(n2n). Imperfect algorithm means that there are some contrived inputs for which the algorithm fails to give the optimal result. Experimental results confirmed that ImDP algorithm performance is better for several data distribution, and for some it improves dramatically ODP-IP. For example, given 27 agents, with ImDP for agentbased uniform distribution time gain is 91% (i.e. 49 minutes).

Coalition formation is one of the most studied topics in multi-agent systems. Central to this endeavor is the problem of partitioning the set of agents into exhaustive and disjoint coalitions so as to maximize social welfare. The coalition structure generation problem is challenging due to the fact that it needs to explore an exponential number of partitions. The fastest exact algorithm to solve this combinatorial optimization problem is ODP-IP [1], which is a hybrid version of two previously established algorithms, namely IDP (Improved Dynamic Programming [2] and IP [3]. Given this, it is desirable to come up with a new algorithm which could build on the same principles as IDP follows and which in turn, improves upon the state. In this paper, we propose a new algorithm EDP (Effective Dynamic Programming). This algorithm is a new design paradigm for this difficult problem. Both EDP and IDP have been implemented and tested on well-known data distribution. We prove that EDP is practically faster than IDP.

The Coalition Structure Generation (CSG) problem is a partitioning of a set of agents into exhaustive and disjoint coalitions to maximize social welfare. This NP-complete problem arises in many practical scenarios. Prominent examples are included in the field of transportation, e-Commerce, distributed sensor networks, and others. The fastest exact algorithm to solve the CSG problem is ODP-IP, which is a hybrid version of two previously established algorithms, namely Improved Dynamic Programming (IDP) and IP. In this paper, we show that the ODP-IP algorithm performs many redundant operations. To improve ODP-IP, we propose a faster abortion mechanism to speed up IP’s search. Our abortion mechanism decides at runtime which of the IP's operations are redundant to skip them. Then, we propose a modified version of IDP (named MIDP) and an improved version of IP (named IIP). Based on these two improved algorithms, we develop a hybrid version (MIDP-IIP) to solve the CSG problem. After a detailed description of the new algorithm MIDP-IIP, an experimental comparison is conducted against ODP-IP. Our analysis shows that MIDP-IIP performs fewer operations than ODP-IP. In addition, MIDP-IIP reduced significantly many problem instances running times (11% to 37 %), and improved drastically some of them.

We consider a smart-city IoT scenario where large crowd may gather temporarily rendering the existing infrastructure inadequate for service consumption. This necessitates a service replication framework over quasi-adhoc scenario using the available computing resources carried by the users such as smart-phones. Such framework can offer fog computing solution in addition to enabling consumption of plethora of new services available with the crowd. In this paper, we propose a service replication scheme that achieves improved service availability, service response-time and system-wide resource utilization compared to the existing ones. The scheme uses a dual-threshold-based proactive sensing mechanism to identify the services which are required to be replicated in immediate future and a multi-agent-based optimal task assignment scheme that enables batch-wise decision making. These mechanisms acting together reduces the service drop rate and improves the system-wide resource utilization. The service response time and the overhead involved in making assignment decisions, are markedly reduced by applying a strategy that combines the benefits of both physical and functional contexts together. An integrated model for analyzing the performance of various generic service replication schemes, is also developed in this paper.

Finding similarity between concepts based on semantics has become a new trend in many applications (e.g., biomedical informatics, natural language processing). Measuring the Semantic Similarity (SS) with higher accuracy is a challenging task. In this context, the Information Content (IC)‐based SS measure has gained popularity over the others. The notion of IC evolves from the science of information theory. Information theory has very high potential to characterize the semantics of concepts. Designing an IC‐based SS framework comprises (i) an IC calculator, and (ii) an SS calculator. In this article, we propose a generic intrinsic IC‐based SS calculator. We also introduce here a new structural aspect of an ontology called DCS (Disjoint Common Subsumers) that plays a significant role in deciding the similarity between two concepts. We evaluated our proposed similarity calculator with the existing intrinsic IC‐based similarity calculators, as well as corpora‐dependent similarity calculators using several benchmark data sets. The experimental results show that the proposed similarity calculator produces a high correlation with human evaluation over the existing state‐of‐the‐art IC‐based similarity calculators.