Abstract
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.
Original language | English |
---|---|
Title of host publication | Intelligent Technologies for Information Analysis |
Editors | Ning Zhong, Liu Jiming |
Publisher | Springer Berlin Heidelberg |
Chapter | 13 |
Pages | 291-310 |
Number of pages | 20 |
ISBN (Electronic) | 9783662079522 |
ISBN (Print) | 9783642073786 |
DOIs | |
Publication status | Published - Jan 2004 |