# Min-k-Cut Coalition Structure Generation on Trust-Utility Relationship Graph

Authors: XiangLong Kong; XiangRong Tong; YingJie Wang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Trust relationships have an important effect on coalition formation. In many real scenarios, agents usually cooperate with others in their trusted social networks to form coalitions. Therefore, the trust value between agents should constrain the utility of forming coalitions when cooperating. At the same time, most studies ignore the impact of the number of coalitions in coalition structure. In this paper, the coalition formation of trust-utility relationship in social networks is researched. Each node represents an agent, and the trust-utility networks that connect the agents constrain coalition formation. To solve the task assignment problem, this paper proposes a greedy algorithm which is based on the edge contraction. Under the premise of ensuring the agent’s individually rationality, this algorithm simulates the formation process of coalitions between agents through continuous edge contraction and constrains the number of forming coalitions tok to solve the problem of coalition structure. Finally, the simulation results show that our algorithm has great scalability because of the ability of solving the coalition structure on a large-scale agent set. It can meet the growing demand for data intensive applications in the Internet of things and artificial intelligence era. The quality of the solution is much higher than other algorithms, and the running time is negligible.


---

## Body

## 1. Introduction

Coalition formation (CF) is an important research area in Multiagent Systems (MAS) [1]. It is known that combining several agents together can achieve goals that every individual cannot achieve alone, or get better utility [2]. Most of CF researches are based on models in the field of cooperative game theory, e.g., characteristic function game [3, 4].Although these models can be used in the study of coalition formation, they are usually too abstract to be used in the actual cooperation scenarios. Most of them use graphs to represent the constraints of the relationship between agents [5–7], and each node in the graph represents an agent, while the edge represents the relationship between agents. Agents can form coalitions only when they are the vertices of the connected subgraphs in a graph, which is called the problem of Graph Coalition Structure Generation (GCSG); that is, in the process of Coalition Structure Generation (CSG), the connectivity between agents that make up the coalition is required. Such constraints exist in most real scenarios, such as social trust constraints, physical constraints [8], and wireless communication constraints [9]. The proposed algorithm in this paper uses trust constraint; agents usually look for others with high trust and utility to cooperate, which is suitable for most scenarios. For example, in the field of privacy protection [10–14], if the trust value or utility between agents is higher, the more privacy data the agents know about each other. Then, the agents in the coalition will not disclose the information between each other and play the role of privacy protection.In addition, most previous studies about the GCSG problem assumed that agents can form any number of coalitions and failed to consider to bind the number of coalitions in a coalition structure. However, in many real scenarios, the number of coalitions should be constrained. For example, in the field of task assignment [15, 16], agents in MAS may need to cooperate to complete all tasks. Since the resources or capabilities of a single agent to perform tasks are limited, it is necessary to assign tasks to the coalition. This requires to constrain the number of coalitions consistent with the number of tasks, so as not to waste resources or fail to complete tasks. In addition, when performing tasks, agents usually do not cooperate with unfamiliar agents, but they can establish contact with other team members through the introduction of trusted agents.To solve the above problems, we develop a solution for the GCSG problem in the context of task assignment and provide a model which can be used to solve the problem of a large number of agents in the real world. We use trust and utility to discuss CF, where the weight of the edge represents the strength of the cooperative relationship between agents, and its weight is represented by two tuples, which are the trust value and utility value, respectively. A connection between disconnected agents can be established through trust transfer. Based on edge contraction, this paper proposes anEdge Contraction Coalition Formation (ECCF) algorithm to solve the GCSG problem. This algorithm refers to the min-k-cut algorithm, constrains the number of formed coalitions to k, and generates the coalition structure under the set conditions. The process of coalition formation between agents is simulated by continuous edge contraction. Each edge contraction process includes the following: (i) delete an edge from the graph, and (ii) merge two nodes previously connected by this edge. Merging two nodes is corresponded to merging two coalitions represented by these nodes, from two coalitions to one coalition, to ensure the generation of a coalition structure with exact k coalitions. The ECCF algorithm is an approximate algorithm with On2e time complexity. In addition, the ECCF algorithm is a greedy algorithm essentially, which can quickly find the feasible solution of the set coalition structure in polynomial time. Finally, ECCF can be applied in large-scale systems. It can well meet the demand of the growing data intensive applications in the Internet of things and artificial intelligence era. The simulation results show that the ECCF algorithm can always find a feasible coalition structure in a short time.The main contributions of this paper are summarized as follows:(1)
Trust is transitive for agents, and each agent is independent. Thesix degrees of separation and trust transfer are used to establish the trust relationship, so as to obtain a trust-utility relationship graph between agents, which can be applied in large-scale agent sets in most real scenarios(2)
In order to solve the problem of task assignment, we propose a new polynomial time complexity algorithm ECCF, which is based on edge contraction and uses the min-k-cut method to segment the trust-utility network graph and generate the coalition structure. Under the condition of ensuring the agent’s individual rationality and generating accurate k coalitions, the coalition structure with k coalitions in the given situation is quickly generated(3)
The simulation results demonstrate the efficiency and runtime of ECCF algorithm. The ECCF algorithm can be applied in large-scale MAS, and its solution quality is much higher than other algorithms; furthermore, its runtime is negligibleThe rest of the paper is organized as follows. Section2 discusses the relationship between our work and existing literature, and Section 3 introduces some Preliminary Definitions. Section 4 formally defines the ECCF, and Section 5 discusses our empirical evaluation. Finally, Section 6 concludes the paper.


## 2. Related Work

In this section, we will discuss the CF, graph theory techniques, and trust transitivity, respectively.


### 2.1. Coalition Formation

Many algorithms have been developed to solve traditional CSG problems. Yeh [17] first proposed the method based on Dynamic Programming (DP) to solve the CSG problem. The exact coalition structure can be obtained through DP. Rahwan et al. [4] developed an anytime algorithm based on the integer partition (IP). Michalak et al. [18] combined the IP algorithm and the DP method to improve the classical CSG algorithm ODP-IP. However, the traditional solutions can only process dozens of agents. To improve the scalability of the algorithm, Ueda et al. [19] have examined alternative function representations, which can reduce the computational complexity of the associated CF problem. Wu et al. [20, 21] sampled the coalition structure graph based on the Monte-Carlo tree search method and iteratively expanded the search tree and proposed a scalable anytime method called CSG-UCT. The CSG-UCT algorithm needs to be performed once for each iteration. The Monte-Carlo tree search process requires a large number of iterations in the process of finding the optimal solution. When the number of agents increases, the time required is greater. However, these models may not be applicable to the real world, such as the scenario in this paper that agents connect through the trust network; that is, they cannot be applied to the GCSG problem.In this context, graph-based cooperative game has attracted the attention of researchers in various fields [22–25]. Voice et al. [26] proposed an algorithm for GCSG. However, the assumption made by voice can only be applied to the characteristic function of the independent disconnected members (IDM) property. It was hard to be applied in most real scenarios. Filippo et al. [27] proposed a branch and bound algorithm CFSS (Coalition Formation for Sparse Synergies), which can solve the problem of GCSG and provide anytime approximate solution of quality guarantees. However, all of these works assumed that any number of coalitions can be formed, and there is no constraint on the number of coalitions in the coalition structure.


### 2.2. Graph Theory Techniques and Trust Transitivity

The ECCF algorithm forms the coalition structure of agent set through edge contraction and constrains the number of coalitions. This graph theory technology and is famous for its application in the algorithm of solving minimum cut problem [28]. Filippo et al. [27] for the first time applied edge contraction to enumerate feasible coalition structure and proposed a CFSS algorithm. At the same time, the search tree is used to represent the search space of the coalition structure. The tree generated by the search space contains all coalition structures on the graph; a CFSS algorithm was proposed, which can prune the search space and solve the coalition structure with quality guarantees at any time when it is used to solve the m+a function coalition structure. However, this algorithm is only suitable for solving the m+a function coalition structure, and it can not be used in the context of task assignment.In the CF game, under the background of task assignment, a social network is mostly used as the constraint of cooperation between agents, which requires connectivity between agents that make up the coalition. Sless et al. [29] avoided this constraint by setting the organizer. Organizers are required to have the ability to promote the connection between unrelated agents. Organizers can add edge sets to social networks to connect unrelated agents, which depends on the social status of organizers and their own experience.In MAS, the research on trust attracted increasing attention of researchers [30–32]. When two parties cooperate, trust is a subjective evaluation of one party to the other. Trust is not only subjective but also asymmetric and transitive. Trust is an important factor in decision-making when an agent chooses who to cooperate with to complete the task. Generally, the higher the trust level, the easier it is to generate a long-term stable cooperative relationship. Trust relationship depends on the network to spread. In the real world, the transitivity of trust can make the unfamiliar agents communicate and promote the cooperation between agents. In this way, in the process of CSG, there is a relationship between agents. At the same time, any coalition generated also has connectivity. Thus, our approach establishes a connection between disconnected agents through trust transfer and then solves the set coalition structure through edge contraction.


## 2.1. Coalition Formation

Many algorithms have been developed to solve traditional CSG problems. Yeh [17] first proposed the method based on Dynamic Programming (DP) to solve the CSG problem. The exact coalition structure can be obtained through DP. Rahwan et al. [4] developed an anytime algorithm based on the integer partition (IP). Michalak et al. [18] combined the IP algorithm and the DP method to improve the classical CSG algorithm ODP-IP. However, the traditional solutions can only process dozens of agents. To improve the scalability of the algorithm, Ueda et al. [19] have examined alternative function representations, which can reduce the computational complexity of the associated CF problem. Wu et al. [20, 21] sampled the coalition structure graph based on the Monte-Carlo tree search method and iteratively expanded the search tree and proposed a scalable anytime method called CSG-UCT. The CSG-UCT algorithm needs to be performed once for each iteration. The Monte-Carlo tree search process requires a large number of iterations in the process of finding the optimal solution. When the number of agents increases, the time required is greater. However, these models may not be applicable to the real world, such as the scenario in this paper that agents connect through the trust network; that is, they cannot be applied to the GCSG problem.In this context, graph-based cooperative game has attracted the attention of researchers in various fields [22–25]. Voice et al. [26] proposed an algorithm for GCSG. However, the assumption made by voice can only be applied to the characteristic function of the independent disconnected members (IDM) property. It was hard to be applied in most real scenarios. Filippo et al. [27] proposed a branch and bound algorithm CFSS (Coalition Formation for Sparse Synergies), which can solve the problem of GCSG and provide anytime approximate solution of quality guarantees. However, all of these works assumed that any number of coalitions can be formed, and there is no constraint on the number of coalitions in the coalition structure.


## 2.2. Graph Theory Techniques and Trust Transitivity

The ECCF algorithm forms the coalition structure of agent set through edge contraction and constrains the number of coalitions. This graph theory technology and is famous for its application in the algorithm of solving minimum cut problem [28]. Filippo et al. [27] for the first time applied edge contraction to enumerate feasible coalition structure and proposed a CFSS algorithm. At the same time, the search tree is used to represent the search space of the coalition structure. The tree generated by the search space contains all coalition structures on the graph; a CFSS algorithm was proposed, which can prune the search space and solve the coalition structure with quality guarantees at any time when it is used to solve the m+a function coalition structure. However, this algorithm is only suitable for solving the m+a function coalition structure, and it can not be used in the context of task assignment.In the CF game, under the background of task assignment, a social network is mostly used as the constraint of cooperation between agents, which requires connectivity between agents that make up the coalition. Sless et al. [29] avoided this constraint by setting the organizer. Organizers are required to have the ability to promote the connection between unrelated agents. Organizers can add edge sets to social networks to connect unrelated agents, which depends on the social status of organizers and their own experience.In MAS, the research on trust attracted increasing attention of researchers [30–32]. When two parties cooperate, trust is a subjective evaluation of one party to the other. Trust is not only subjective but also asymmetric and transitive. Trust is an important factor in decision-making when an agent chooses who to cooperate with to complete the task. Generally, the higher the trust level, the easier it is to generate a long-term stable cooperative relationship. Trust relationship depends on the network to spread. In the real world, the transitivity of trust can make the unfamiliar agents communicate and promote the cooperation between agents. In this way, in the process of CSG, there is a relationship between agents. At the same time, any coalition generated also has connectivity. Thus, our approach establishes a connection between disconnected agents through trust transfer and then solves the set coalition structure through edge contraction.


## 3. Preliminary Definitions

LetG=A,E,ρ,ω represent a directed weighted graph, where A=a1,a2,⋯,an is a finite, non-empty set of agents. Each edge ai,aj∈E has two weights ρ and ω, which represent trust and utility relationship between agents, respectively. ρi,j represents the trust value of agent ai from aj, and ωi,j represents the utility value of agent ai from aj. Agents without edge connection can get the trust value and utility value through transfer calculation.Letfρ,ωai,aj represent the trust-utility relationship function obtained by considering the trust relationship and utility relationship between agent ai and agent aj, which represents the ability of smooth cooperation between agents. fρ,ωai,aj could be expressed by
(1)fρ,ωai,aj=Pi,jΩi,j+Pj,iΩj,i2.where P and Ω are the trust relationship and utility relationship between agents after transmission. The trust-utility relationship can be used to get the trust-utility relationship graph between agents Gf=A,E,f. Only the trust relationship between agents is considered when ω is zero or the same between agents in cooperation. Only the utility relationship is considered in turn when ρ is zero or the same between agents in cooperation.Letμai,C denote the utility ai∈C; its value is the sum of the utility among ai and other members in C. It is shown by
(2)μai,C=∑ai∈Cωai,aj.It is denoted asμi. The utility of an agent is given by other agents who have trust-utility relationship with him in the coalition. The utility of a coalition is composed of the utility of all agents in the coalition. VC is used to represent the value of C∈A in the coalition, and the value is defined as the values of all agents in C. VC is obtained by
(3)VC=∑ai∈Cμai,C.Assume that the required number of tasks to be completed by agents isk,0<k<n. SkA indicates that the agent set A is divided into a set of partitions containing k nonempty subsets. Each case in SkA is called the coalition structure, which is denoted as CS.γCS:A⟶CS represents the mapping function of the agent set to its coalition, i.e., CS∈SkA, Ci∈CS, and ai∈Ci, then γCSai=Ci. The utility of agents in different coalition structures is shown by Figure 1. The social utility of coalition structure CS is defined as SWCS, which is shown by
(4)SWCS=∑C∈CSVC.Definition 1 (block).
Given a coalition structureCS=C1,C2,⋯,Ck, ∃B∈A, if ∀ai,aj∈B, ∀ai′∈γCSai, ∀aj′∈γCSaj satisfied fρ,ωai,aj>fρ,ωai,ai′ and fρ,ωai,aj>fρ,ωaj,aj′; then, a coalition B is block.
According to Definition1, for any two agents in a coalition, if there is another coalition B containing the two agents and the rewards of agent in B are greater than the rewards of the current coalition, that is, these two agents tend to leave the current coalition, and B is called block. Clearly, blockB is an unstable factor for CS.
From Figure2, we can see that if there is a coalition structure CS=a1,a2,a3,a4,a5,a6, a coalition B=a4,a5. According to Definition 1, we can see that coalition B is a block.
Note that even if the optimal CS is obtained, there may beblocks in the solution. The movement of agents in the original coalition may form any number of coalitions. Clearly, we must exclude this situation in the model. Therefore, a k-block coalition must be defined so that the final coalition structure contains exactly k coalitions.Definition 2 (k-block coalition).
Given a coalition structureCS=C1,C2,⋯,Ck, ∃B∈A, if ∀ai,aj∈B, ∀ai′∈γCSai, ∀aj′∈γCSaj can satisfy fρ,ωai,aj>fρ,ωai,ai′ and fρ,ωai,aj>fρ,ωaj,aj′. At the same time, ∃Cm∈CS, Cm∈B; then a coalition B is k-block.
In Figure2, it is known that there are coalition structure CS=a1,a2,a3,a4,a5,a6 and blockB=a4,a5, ∃Cm=a4, making Cm∈CS and Cm∈B. According to Definition 2, B is a 3-block coalition.
Definition2 is an extension of Definition 1. Coalition structure after any agent movement must contain exact k coalitions. Therefore, it is necessary to ensure that agents tend to join the existing coalition; that is, agents with movement tendency in the coalition structure will only join the current coalition to another formed coalition and will not form a new coalition. In addition, it is necessary to ensure that there is only one coalition. If there are multiple such coalitions, the number of coalitions in the generated coalition structure will be less than k. If there is less than one such coalition, the final coalition structure will contain k+1 coalitions. Only if there is one coalition, the movement of agents will guarantee the coalition structure to contain accurate k coalitions.Definition 3 (individual rationality).
Given a coalition structureCS∈SkA, if each agent gets at least the same utility from CS to its own, then CS satisfies individual rationality, i.e., ∀a∈Ci, i∈1,⋯,k, μai,Ci≥μa,a.Definition 4 (trust transfer).
Given the trust network, trust can be transferred. As shown in Figure3, assuming that agent a1 trusts agent a2 and agent a2 trusts agent a4, it can be determined that agent a1 may trust agent a4. There are two ways for trust transfer: (i) take the minimum value, and (ii) take the weighted average value. In a large network system, the weighted average will make the trust value tend to zero, so we take the minimum value in the transfer process, that is,
(5)Pi,j=minρijk,k=2,3,⋯,5.
In the same way, the utility between agents is expressed as follows:(6)Ωi,j=minωijk,k=2,3,⋯,5.
According to the trust and utility function, trust and utility relationship between the agents can be obtained after coherently considering the trust relationship and utility relationship, so as to obtain the trust-utility relationship graphGf=A,E,f between the agents, where A represents the agent set, the members are generally ai, E is the edge set, and each edge e has weight f that represents the trust-utility relationship value between the agents obtained through the trust-utility function.
The trust network in Figure2 can provide an example of trust transfer. According to the equations, we can get P15=0.6, Ω15=10, and f15=6.Definition 5 (edge contraction).
Given the trust-utility graphGf=A,E,f, ai,aj∈E, the result of contraction for e is the graph Gf′ obtained by deleting e and corresponding vertices ai and aj and, at the same time, adding new vertices m=ai∪aj. In addition, each edge connecting with ai or aj in Gf will be connected to m in Gf′, then merging the parallel edges (i.e., the edges connected to the combined two vertices) and the corresponding weights of parallel edges (i.e., the trust-utility relationship).
Intuitively, each edge contraction merges two vertices, corresponding to merging two coalitions represented by these nodes. Note that the order of the contraction of edges can be in any given order and get the same result, i.e., contractinge first, then contracting e′ which produces the same graph to contracting e′ then contracting e. The resulting graph after contracting represents a feasible coalition structure, where the coalition corresponds to the vertices of the graph.
When performing edge contraction, the number of subsets of edges in the graph is greater than the number of feasible coalition structures. This redundancy is due to the contraction of any two or three edges resulting in the same coalition structure. In this paper, the edge with the largest weight is firstly selected for contraction operation. When the weight of the edge is different, there will be no redundant operation. When there are multiple edges with the largest weight, any edge with the largest weight will be contracted randomly, and the edge with the largest weight will be also selected for operation in the next contraction. So there will be no redundant coalition structure.Figure 1
The utility of agents in different coalition structures.Figure 2
Trust network.Figure 3
Example of an edge contraction.
(a)(b)Figure3 shows the contraction of the edge a1,a2 in the trust-utility graph Gf=A,E,f, which results in a new vertex m=ai∪aj connected to the vertex a3 and merges the parallel edges a1,a3 and a2,a3.


## 4. Maximize the Utility of Coalition Structure

This section mainly discusses the problem of the coalition structure that tries to maximize the utility given a trust-utility relationship graph. Agents in the graph are reasonably assigned to coalitions to maximize the utility of coalition structure.Definition 6 (k-cut).
CutkC1,C2,⋯,Ck means that agents in the trust-utility relationship graph are divided into k disjoint parts according to the trust-utility relationship, where each part forms a coalition, and k coalitions are formed. CutkC1,C2,⋯,Ck is called k-cut.Brânzei and Larson [33] first noted the relationship between the social welfare maximization coalition structure and the min-k-cut of the graph; that is, the coalition structure with the number k of maximizing utility is the partition of the min-k-cut graph. This is reasonable because the sum of the weights of all edges is constant. By minimizing the utility of edges outside the coalition, the utility within the coalition can be maximized. Therefore, the min-k-cut algorithm can be used to find the maximum utility coalition structure. Based on the above researches, Sless et al. [29] proved that min-k-cut is in P for nearly positive graphs and a fixed k. However, the algorithm has high complexity and can only be applied in nearly positive graphs, while our algorithm could solve approximate solutions with low complexity.Based on the concept of edge contraction in graph theory, an approximate algorithm is proposed. Givenk, the edge contraction method is used to perform n-k number of edge contraction. Therefore, it is ended with k nodes. Intuitively, each node after the contraction is a coalition. Therefore, though deleting the remaining edge, it can form k-connected subgraphs, i.e., k coalitions.In each iterative contraction, the edge with the largest weight is selected in the trust-utility graph, and define operationContractai,aj. Contractai,aj means to delete points aiand aj and edge ai,aj, and add a new nodes m=ai∪aj, for any a∈A; there is fρ,ωa,m=fρ,ωm,a=fρ,ωai,a+fρ,ωaj,a.


### 4.1. ECCF

In this section, we give a comprehensive consideration for the trust relationship and utility relationship between the agents in the trust networkG; then Pi,j and ωi,j are calculated according to the trust network G. Then, the trust-utility relationship between the agents is calculated according to the values of Pi,j and ωi,j. Moreover, the contract of edge is performed according to f to complete the image cutting. Finally, coalition structure is obtained. The specific steps are as shown by Algorithm 1.Algorithm 1: ECCF
Input: Trust network G = (A,E,ρ,ω), number of coalitions parameter k from CSOutput: Coalition structure CS1: Calculate the trust and utility after transfer2: For all agentai,aj∈A3:Pi,j=minρijk,k=2,3,⋯,5.4:Ωi,j=minωijk,k=2,3,⋯,5.5: End for6: Calculate the trust and utility relationship and get the trust-utility relationship graph7: For each edgeai,aj∈E8:fρ,ωai,aj=Pi,jΩi,j+Pj,iΩj,i/2.9: End for10: Perform the edge contraction operation and generate the image segmentation coalition11: For all Agentai,aj∈A12: Fori =1…n-k13:ai,aj←maxfρ,ωai,aj14:Contractai,aj15:  For alla∈A16:fρ,ωa,m=fρ,ωai,a+fρ,ωaj,a17:  End for18: End for19: For each edgeai,aj∈E20:  Removeai,aj21: End for22: End for23:returnCSGiven the trust networkG=A,E,ρ,ω, the number of vertices is n, the Pi,j, Ωi,j, and fi,jai,aj are the trust relationship, the utility relationship, and the trust-utility relationship after comprehensive consideration, respectively. Firstly, input the trust network and calculate the trust value and utility value between agents according to the trust transfer formula. Secondly, according to the results of the first step, the trust and utility are considered synthetically, and the trust-utility relationship between agents is obtained by using the trust-utility relationship function. Thirdly, according to the trust-utility relationship size, the proposed algorithm is performed, and according to the operation of edge contraction, n-k times edge contraction is performed, then the remaining weight is deleted, and the image is cut. The agent set is divided into k disjoint sets, i.e., k coalitions, and the final CS is obtained.In each iteration of ECCF algorithm, the edge with the largest trust-utility relationship between agents is selected to contract. The CS obtained by the ECCF algorithm is an approximate solution, which is essentially a greedy algorithm. The ECCF algorithm does not pursue the optimal solution, and backtrack only hopes to get a more satisfactory solution quickly and makes the optimal selection based on the current situation, without considering all possible overall situations. It could save a lot of time to find the best solution.


#### 4.1.1. Time Complexity Analysis

In the ECCF algorithm, the first step uses the trust transfer formula to obtain the trust value and utility value between agents. The time complexity isOe. In the second step, the trust-utility function formula is used to coherently consider calculate the trust-utility relationship between agents. The time complexity is O(n2). In the third step, the for loop in the algorithm performs the contract operation n-k times. In each contract iteration, the ECCF algorithm is used to traverse all edges in the graph and find the largest weight edge. The time complexity is Oe. Finally, merge parallel edges and the corresponding weights of parallel edges. The complexity is at most O2n, so the complexity of the third step is O(n2e). The total time complexity of the algorithm is O(n2e).


#### 4.1.2. Example of Algorithm Solving Process

Figure4 shows an ECCF algorithm for a given simple trust network.Figure 4
Simple trust network.According to the ECCF algorithm, the solution process is explained as follows:In the first step, the settings are initialized, which are shown in Table1.Table 1
Initialization trust-utility.
a1a2a3a1[0.2, 3]a2[0.2, 3][0.8, 8]a3[0.8, 8]In the second step, according to the transfer formula, the trust and utility after processing are shown in Table2.Table 2
Postprocessing trust-utility.
a1a2a3a1[0.2, 3][0.2, 3]a2[0.2, 3][0.8, 8]a3[0.2, 3][0.8, 8]In the third step, we use the trust-utility functionfρ,ωai,aj=Pi,jΩi,j+Pj,iΩj,i/2 to get the relationship shown in Table 3.Table 3
Trust-utility function postrelationship.
a1a2a3a10.60.6a20.66.4a30.66.4The ECCF algorithm coherently considers the impact of the trust relationship and utility relationship between agents, which is consistent with the real social situation, and obtains the trust-utility relationship graph shown by Figure5.Figure 5
Trust-utility relationship graph.
(a)
Before contraction(b)
After contractionIn the fourth step, based on the ECCF algorithm, letk=2; we contract the maximum edge (i.e., 6.4) and delete the remaining trust-utility relationship (i.e., 2.52) to get the coalition structure a1,a2,a3; then the utility is 12.8.


## 4.1. ECCF

In this section, we give a comprehensive consideration for the trust relationship and utility relationship between the agents in the trust networkG; then Pi,j and ωi,j are calculated according to the trust network G. Then, the trust-utility relationship between the agents is calculated according to the values of Pi,j and ωi,j. Moreover, the contract of edge is performed according to f to complete the image cutting. Finally, coalition structure is obtained. The specific steps are as shown by Algorithm 1.Algorithm 1: ECCF
Input: Trust network G = (A,E,ρ,ω), number of coalitions parameter k from CSOutput: Coalition structure CS1: Calculate the trust and utility after transfer2: For all agentai,aj∈A3:Pi,j=minρijk,k=2,3,⋯,5.4:Ωi,j=minωijk,k=2,3,⋯,5.5: End for6: Calculate the trust and utility relationship and get the trust-utility relationship graph7: For each edgeai,aj∈E8:fρ,ωai,aj=Pi,jΩi,j+Pj,iΩj,i/2.9: End for10: Perform the edge contraction operation and generate the image segmentation coalition11: For all Agentai,aj∈A12: Fori =1…n-k13:ai,aj←maxfρ,ωai,aj14:Contractai,aj15:  For alla∈A16:fρ,ωa,m=fρ,ωai,a+fρ,ωaj,a17:  End for18: End for19: For each edgeai,aj∈E20:  Removeai,aj21: End for22: End for23:returnCSGiven the trust networkG=A,E,ρ,ω, the number of vertices is n, the Pi,j, Ωi,j, and fi,jai,aj are the trust relationship, the utility relationship, and the trust-utility relationship after comprehensive consideration, respectively. Firstly, input the trust network and calculate the trust value and utility value between agents according to the trust transfer formula. Secondly, according to the results of the first step, the trust and utility are considered synthetically, and the trust-utility relationship between agents is obtained by using the trust-utility relationship function. Thirdly, according to the trust-utility relationship size, the proposed algorithm is performed, and according to the operation of edge contraction, n-k times edge contraction is performed, then the remaining weight is deleted, and the image is cut. The agent set is divided into k disjoint sets, i.e., k coalitions, and the final CS is obtained.In each iteration of ECCF algorithm, the edge with the largest trust-utility relationship between agents is selected to contract. The CS obtained by the ECCF algorithm is an approximate solution, which is essentially a greedy algorithm. The ECCF algorithm does not pursue the optimal solution, and backtrack only hopes to get a more satisfactory solution quickly and makes the optimal selection based on the current situation, without considering all possible overall situations. It could save a lot of time to find the best solution.


### 4.1.1. Time Complexity Analysis

In the ECCF algorithm, the first step uses the trust transfer formula to obtain the trust value and utility value between agents. The time complexity isOe. In the second step, the trust-utility function formula is used to coherently consider calculate the trust-utility relationship between agents. The time complexity is O(n2). In the third step, the for loop in the algorithm performs the contract operation n-k times. In each contract iteration, the ECCF algorithm is used to traverse all edges in the graph and find the largest weight edge. The time complexity is Oe. Finally, merge parallel edges and the corresponding weights of parallel edges. The complexity is at most O2n, so the complexity of the third step is O(n2e). The total time complexity of the algorithm is O(n2e).


### 4.1.2. Example of Algorithm Solving Process

Figure4 shows an ECCF algorithm for a given simple trust network.Figure 4
Simple trust network.According to the ECCF algorithm, the solution process is explained as follows:In the first step, the settings are initialized, which are shown in Table1.Table 1
Initialization trust-utility.
a1a2a3a1[0.2, 3]a2[0.2, 3][0.8, 8]a3[0.8, 8]In the second step, according to the transfer formula, the trust and utility after processing are shown in Table2.Table 2
Postprocessing trust-utility.
a1a2a3a1[0.2, 3][0.2, 3]a2[0.2, 3][0.8, 8]a3[0.2, 3][0.8, 8]In the third step, we use the trust-utility functionfρ,ωai,aj=Pi,jΩi,j+Pj,iΩj,i/2 to get the relationship shown in Table 3.Table 3
Trust-utility function postrelationship.
a1a2a3a10.60.6a20.66.4a30.66.4The ECCF algorithm coherently considers the impact of the trust relationship and utility relationship between agents, which is consistent with the real social situation, and obtains the trust-utility relationship graph shown by Figure5.Figure 5
Trust-utility relationship graph.
(a)
Before contraction(b)
After contractionIn the fourth step, based on the ECCF algorithm, letk=2; we contract the maximum edge (i.e., 6.4) and delete the remaining trust-utility relationship (i.e., 2.52) to get the coalition structure a1,a2,a3; then the utility is 12.8.


## 4.1.1. Time Complexity Analysis

In the ECCF algorithm, the first step uses the trust transfer formula to obtain the trust value and utility value between agents. The time complexity isOe. In the second step, the trust-utility function formula is used to coherently consider calculate the trust-utility relationship between agents. The time complexity is O(n2). In the third step, the for loop in the algorithm performs the contract operation n-k times. In each contract iteration, the ECCF algorithm is used to traverse all edges in the graph and find the largest weight edge. The time complexity is Oe. Finally, merge parallel edges and the corresponding weights of parallel edges. The complexity is at most O2n, so the complexity of the third step is O(n2e). The total time complexity of the algorithm is O(n2e).


## 4.1.2. Example of Algorithm Solving Process

Figure4 shows an ECCF algorithm for a given simple trust network.Figure 4
Simple trust network.According to the ECCF algorithm, the solution process is explained as follows:In the first step, the settings are initialized, which are shown in Table1.Table 1
Initialization trust-utility.
a1a2a3a1[0.2, 3]a2[0.2, 3][0.8, 8]a3[0.8, 8]In the second step, according to the transfer formula, the trust and utility after processing are shown in Table2.Table 2
Postprocessing trust-utility.
a1a2a3a1[0.2, 3][0.2, 3]a2[0.2, 3][0.8, 8]a3[0.2, 3][0.8, 8]In the third step, we use the trust-utility functionfρ,ωai,aj=Pi,jΩi,j+Pj,iΩj,i/2 to get the relationship shown in Table 3.Table 3
Trust-utility function postrelationship.
a1a2a3a10.60.6a20.66.4a30.66.4The ECCF algorithm coherently considers the impact of the trust relationship and utility relationship between agents, which is consistent with the real social situation, and obtains the trust-utility relationship graph shown by Figure5.Figure 5
Trust-utility relationship graph.
(a)
Before contraction(b)
After contractionIn the fourth step, based on the ECCF algorithm, letk=2; we contract the maximum edge (i.e., 6.4) and delete the remaining trust-utility relationship (i.e., 2.52) to get the coalition structure a1,a2,a3; then the utility is 12.8.


## 5. Simulation Experiments and Analysis

### 5.1. Experimental Environment and Comparison Algorithm

In this section, the simulation experiments are designed to demonstrate the effectiveness of the ECCF algorithm. We use a random graph for experimental data. The experimental environment is Windows 7 with 64 bit operating system, 8GB memory, 3.2GHz main frequency, and i5-6500 processor. The programming language is java, which runs on eclipse.We chose the classic CSG algorithm as the comparison algorithm, with the DP algorithm and ODP-IP algorithm. In addition, we also implement the efficient algorithm of Saran and Vazirani [34] which is called SV (Saran and Vazirani) algorithm. The SV algorithm is an approximate algorithm for solving min-k-cut problem. The algorithm recursively selects the edge with the smallest weight to cut until the graph is divided into k parts.We use utility and runtime as indexes to evaluate the coalition structure. On the one hand, we study the influence of trust, the number of agents isn, and the number of coalitions is k on the utility of CS. On another hand, we study the influence of the number of agents n and the number of coalitions k on runtime.


### 5.2. Experimental Results and Performance Analysis

#### 5.2.1. Effect ofρ,n,k on Utility

This section mainly discusses the influence of trust, the number of agentsn, and the number of coalitions k for the ECCF algorithm on the utility of the coalition structure. Among them, 0<ρ<0.5 is a low trust relationship, 0.5<ρ<1 is a high trust relationship, and 0<ρ<1 is a high-low trust relationship.Figure6 shows the relationship between trust and utility among agents in the trust-utility graph of the ECCF algorithm, where the x-coordinate represents the number of agents and the y-coordinate represents the utility of the ECCF algorithm. It is easy to know that trust and utility between agents show a linear relationship. The utility generated by the agent increases with the increase of the trust relationship. The greater the trust value between agents, the greater the utility of generating the coalition structure. In addition, the utility of the coalition structure is related to the number of agents. Figure 7 shows the relationship between agents and the utility of the coalition structure in ECCF algorithm. In general, the utility of the coalition structure increases with the number of agents. Through the analysis of Figure 7, it is easy to known that the utilities of the ECCF algorithm and the DP algorithm increase with the number of agents; the increase range is basically the same. Figure 8 shows the relationship among k coalitions in CS and the utility of coalition structure. The x-coordinate shows the number of coalitions in CS, and the y-coordinate shows the utility of CS. With the increase of k, the utility of ECCF algorithm decreases correspondingly, because the number of edges that need to be contracted decreases correspondingly and the number of edges that need to be deleted finally increases, so the final remaining utility decreases correspondingly.Figure 6
The influence of trust on utility.Figure 7
The influence ofn on utility.Figure 8
The influence ofn and k on utility.


#### 5.2.2. Effect ofn and k on Runtime

This section mainly discusses the effect of the number of agentsn and the number of tasks k on runtime of the generated coalition structure. Through the trust-utility relationship graph, the coalition structure of different agent sets is solved, and the runtime required to generate the coalition structure is recorded. The results are shown in Figure 9. The x-coordinate is the number of agents, and the y-coordinate is the runtime of the Coalition Structure Generation; the unit is millisecond.Figure 9
Relationship between the number of agents and runtime.
(a)(b)Through the analysis of Figure9, it is easy to know that with the increase of the number of agents, the runtime of ECCF algorithm increases correspondingly and the runtime is not affected by the trust relationship. According to Figure 10, it is easy to know that with the increase of the number of k, the runtime of the ECCF algorithm decreases correspondingly, because the number of edges that need to be contracted decreases correspondingly, so the calculation amount decreases correspondingly. Similarly, it is not affected by the trust relationship; that is, the trust between agents only affects the utility of the formed coalition and does not affect the runtime of the coalition.Figure 10
Relationship between the number of coalitions and runtime.
(a)(b)


#### 5.2.3. Algorithm Runtime Comparison

This section mainly discusses the changes on the runtime of the ECCF algorithm, DP algorithm, and ODP-IP algorithm with the increase of the number of agents. The comparison results are shown in Figure11. The x-coordinate represents the number of agents, and the y-coordinate represents the runtime.Figure 11
Runtime comparison of three algorithms.In Figure11, it can be see that the runtime of the ECCF algorithm is far less than those of the DP algorithm and ODP-IP algorithm. Since the DP algorithm gradually decomposes the current solution into an optimal partition and records the intermediate solution to find the optimal coalition structure, the running time is relatively high. In addition, with the increase of the number of agents, the effect of time comparison is more obvious.


#### 5.2.4. Algorithm Utility Comparison

From Figure12, we can see that the utility of the coalition structure obtained by the ECCF algorithm is greater than that by the SV algorithm. In addition, with the increase of the number of agents, the effect of utility is more obvious. Because the SV algorithm recursively deletes the edge of the minimum trust-utility relationship until k coalitions are obtained. Then, the minimum trust-utility relationship among agents in the generated k coalitions will also be deleted, which will cause the waste of resources. The utility generated by the SV algorithm is less than that by the ECCF algorithm in most cases.Figure 12
Utility comparison of two algorithms.


## 5.1. Experimental Environment and Comparison Algorithm

In this section, the simulation experiments are designed to demonstrate the effectiveness of the ECCF algorithm. We use a random graph for experimental data. The experimental environment is Windows 7 with 64 bit operating system, 8GB memory, 3.2GHz main frequency, and i5-6500 processor. The programming language is java, which runs on eclipse.We chose the classic CSG algorithm as the comparison algorithm, with the DP algorithm and ODP-IP algorithm. In addition, we also implement the efficient algorithm of Saran and Vazirani [34] which is called SV (Saran and Vazirani) algorithm. The SV algorithm is an approximate algorithm for solving min-k-cut problem. The algorithm recursively selects the edge with the smallest weight to cut until the graph is divided into k parts.We use utility and runtime as indexes to evaluate the coalition structure. On the one hand, we study the influence of trust, the number of agents isn, and the number of coalitions is k on the utility of CS. On another hand, we study the influence of the number of agents n and the number of coalitions k on runtime.


## 5.2. Experimental Results and Performance Analysis

### 5.2.1. Effect ofρ,n,k on Utility

This section mainly discusses the influence of trust, the number of agentsn, and the number of coalitions k for the ECCF algorithm on the utility of the coalition structure. Among them, 0<ρ<0.5 is a low trust relationship, 0.5<ρ<1 is a high trust relationship, and 0<ρ<1 is a high-low trust relationship.Figure6 shows the relationship between trust and utility among agents in the trust-utility graph of the ECCF algorithm, where the x-coordinate represents the number of agents and the y-coordinate represents the utility of the ECCF algorithm. It is easy to know that trust and utility between agents show a linear relationship. The utility generated by the agent increases with the increase of the trust relationship. The greater the trust value between agents, the greater the utility of generating the coalition structure. In addition, the utility of the coalition structure is related to the number of agents. Figure 7 shows the relationship between agents and the utility of the coalition structure in ECCF algorithm. In general, the utility of the coalition structure increases with the number of agents. Through the analysis of Figure 7, it is easy to known that the utilities of the ECCF algorithm and the DP algorithm increase with the number of agents; the increase range is basically the same. Figure 8 shows the relationship among k coalitions in CS and the utility of coalition structure. The x-coordinate shows the number of coalitions in CS, and the y-coordinate shows the utility of CS. With the increase of k, the utility of ECCF algorithm decreases correspondingly, because the number of edges that need to be contracted decreases correspondingly and the number of edges that need to be deleted finally increases, so the final remaining utility decreases correspondingly.Figure 6
The influence of trust on utility.Figure 7
The influence ofn on utility.Figure 8
The influence ofn and k on utility.


### 5.2.2. Effect ofn and k on Runtime

This section mainly discusses the effect of the number of agentsn and the number of tasks k on runtime of the generated coalition structure. Through the trust-utility relationship graph, the coalition structure of different agent sets is solved, and the runtime required to generate the coalition structure is recorded. The results are shown in Figure 9. The x-coordinate is the number of agents, and the y-coordinate is the runtime of the Coalition Structure Generation; the unit is millisecond.Figure 9
Relationship between the number of agents and runtime.
(a)(b)Through the analysis of Figure9, it is easy to know that with the increase of the number of agents, the runtime of ECCF algorithm increases correspondingly and the runtime is not affected by the trust relationship. According to Figure 10, it is easy to know that with the increase of the number of k, the runtime of the ECCF algorithm decreases correspondingly, because the number of edges that need to be contracted decreases correspondingly, so the calculation amount decreases correspondingly. Similarly, it is not affected by the trust relationship; that is, the trust between agents only affects the utility of the formed coalition and does not affect the runtime of the coalition.Figure 10
Relationship between the number of coalitions and runtime.
(a)(b)


### 5.2.3. Algorithm Runtime Comparison

This section mainly discusses the changes on the runtime of the ECCF algorithm, DP algorithm, and ODP-IP algorithm with the increase of the number of agents. The comparison results are shown in Figure11. The x-coordinate represents the number of agents, and the y-coordinate represents the runtime.Figure 11
Runtime comparison of three algorithms.In Figure11, it can be see that the runtime of the ECCF algorithm is far less than those of the DP algorithm and ODP-IP algorithm. Since the DP algorithm gradually decomposes the current solution into an optimal partition and records the intermediate solution to find the optimal coalition structure, the running time is relatively high. In addition, with the increase of the number of agents, the effect of time comparison is more obvious.


### 5.2.4. Algorithm Utility Comparison

From Figure12, we can see that the utility of the coalition structure obtained by the ECCF algorithm is greater than that by the SV algorithm. In addition, with the increase of the number of agents, the effect of utility is more obvious. Because the SV algorithm recursively deletes the edge of the minimum trust-utility relationship until k coalitions are obtained. Then, the minimum trust-utility relationship among agents in the generated k coalitions will also be deleted, which will cause the waste of resources. The utility generated by the SV algorithm is less than that by the ECCF algorithm in most cases.Figure 12
Utility comparison of two algorithms.


## 5.2.1. Effect ofρ,n,k on Utility

This section mainly discusses the influence of trust, the number of agentsn, and the number of coalitions k for the ECCF algorithm on the utility of the coalition structure. Among them, 0<ρ<0.5 is a low trust relationship, 0.5<ρ<1 is a high trust relationship, and 0<ρ<1 is a high-low trust relationship.Figure6 shows the relationship between trust and utility among agents in the trust-utility graph of the ECCF algorithm, where the x-coordinate represents the number of agents and the y-coordinate represents the utility of the ECCF algorithm. It is easy to know that trust and utility between agents show a linear relationship. The utility generated by the agent increases with the increase of the trust relationship. The greater the trust value between agents, the greater the utility of generating the coalition structure. In addition, the utility of the coalition structure is related to the number of agents. Figure 7 shows the relationship between agents and the utility of the coalition structure in ECCF algorithm. In general, the utility of the coalition structure increases with the number of agents. Through the analysis of Figure 7, it is easy to known that the utilities of the ECCF algorithm and the DP algorithm increase with the number of agents; the increase range is basically the same. Figure 8 shows the relationship among k coalitions in CS and the utility of coalition structure. The x-coordinate shows the number of coalitions in CS, and the y-coordinate shows the utility of CS. With the increase of k, the utility of ECCF algorithm decreases correspondingly, because the number of edges that need to be contracted decreases correspondingly and the number of edges that need to be deleted finally increases, so the final remaining utility decreases correspondingly.Figure 6
The influence of trust on utility.Figure 7
The influence ofn on utility.Figure 8
The influence ofn and k on utility.


## 5.2.2. Effect ofn and k on Runtime

This section mainly discusses the effect of the number of agentsn and the number of tasks k on runtime of the generated coalition structure. Through the trust-utility relationship graph, the coalition structure of different agent sets is solved, and the runtime required to generate the coalition structure is recorded. The results are shown in Figure 9. The x-coordinate is the number of agents, and the y-coordinate is the runtime of the Coalition Structure Generation; the unit is millisecond.Figure 9
Relationship between the number of agents and runtime.
(a)(b)Through the analysis of Figure9, it is easy to know that with the increase of the number of agents, the runtime of ECCF algorithm increases correspondingly and the runtime is not affected by the trust relationship. According to Figure 10, it is easy to know that with the increase of the number of k, the runtime of the ECCF algorithm decreases correspondingly, because the number of edges that need to be contracted decreases correspondingly, so the calculation amount decreases correspondingly. Similarly, it is not affected by the trust relationship; that is, the trust between agents only affects the utility of the formed coalition and does not affect the runtime of the coalition.Figure 10
Relationship between the number of coalitions and runtime.
(a)(b)


## 5.2.3. Algorithm Runtime Comparison

This section mainly discusses the changes on the runtime of the ECCF algorithm, DP algorithm, and ODP-IP algorithm with the increase of the number of agents. The comparison results are shown in Figure11. The x-coordinate represents the number of agents, and the y-coordinate represents the runtime.Figure 11
Runtime comparison of three algorithms.In Figure11, it can be see that the runtime of the ECCF algorithm is far less than those of the DP algorithm and ODP-IP algorithm. Since the DP algorithm gradually decomposes the current solution into an optimal partition and records the intermediate solution to find the optimal coalition structure, the running time is relatively high. In addition, with the increase of the number of agents, the effect of time comparison is more obvious.


## 5.2.4. Algorithm Utility Comparison

From Figure12, we can see that the utility of the coalition structure obtained by the ECCF algorithm is greater than that by the SV algorithm. In addition, with the increase of the number of agents, the effect of utility is more obvious. Because the SV algorithm recursively deletes the edge of the minimum trust-utility relationship until k coalitions are obtained. Then, the minimum trust-utility relationship among agents in the generated k coalitions will also be deleted, which will cause the waste of resources. The utility generated by the SV algorithm is less than that by the ECCF algorithm in most cases.Figure 12
Utility comparison of two algorithms.


## 6. Conclusions

In this paper, we use a given number of coalitions to analyze the trust and utility of CSG. This paper proposed an ECCF algorithm based on edge contraction, which can solve the GCSG problem well. Firstly, trust is transitive, and the trust and utility are transferred according to the trust transfer. Then, the image of the transferred trust network is segmented to obtain a feasible coalition structure. Finally, the ECCF algorithm can be applied to large-scale systems, and the feasible solution can be obtained quickly.In future works, we will analyze the search problem of the coalition core in the coalition structure. Another potential research direction is the study of the number of agents in coalition. In order to remove the coalition with a small number of agents in the solution, the size of the coalition can be limited.



---

*Source: 8834879-2021-04-14.xml*