Agent Networks: Topological and Clustering Characterization

In this chapter, we will introduce the notion of an agent network and its topology. Further, we will show how to model the computational complexity of distributed problem solving by means of studying the topological and clustering characteristics of agent networks formed by multi-agent systems. Specifically, we will examine two multi-agent-based representations for satisfiability problems (SATs), i.e., agents representing clauses and agents representing variables, and experimentally characterize the topologies of the resulting agent networks. Based on the experimental results, we will study how different topologies reflect the computational complexities of agent networks, and further discuss how to balance complexities in intra- and inter-agent computations. In the above studies, random agent networks are used to compare with real-world agent networks. Particularly, the clustering characteristic is one of the properties used to differentiate between real-world agent networks and random agent networks. In order to provide a quantitative measurement for characterizing random agent networks, we will study their clustering characteristics, focusing on the average value and lower bounds of clustering coefficients.