(581f) Descriptors For Modeling Undirected Networks

Particle Swarm Optimization [1] (PSO) is a biologically inspired optimization technique that uses a swarm of particles to explore a function space in order to locate an optimum. PSO has its roots in artificial life, social sciences and computer science [2]. While it is easy to simulate the swarm searching for the global minimum and compute the accuracy of such a search but, given the topological connectivity of the swarm we cannot predict what the accuracy will be. The behavior of the swarm in any function space is primarily dependent on the topological connectivity of the nodes. The topological connectivity is described by an undirected network, which in turn can be represented in an adjacency matrix. This requires n2 numbers where n is the number of nodes. Using the adjacency matrix itself does not immediately give insight into the underlying information propagation mechanism and the ultimate behavior of the swarm. Hence we need to reduce the dimensionality of the system and come up with a set of network descriptors that capture the essence of the network and can be used to model the behavior of the swarm.

Reduction of dimensions will lead to loss of information. Although the descriptors are not unique, the dimensionality reduction makes it easy to compare and analyze the networks. This is used in different applications such as Quantitative Structure Activity Relationship [3]. There are two main requirements for any descriptor to be useful. 1) The descriptor should be unique for a network. 2) The descriptor must be close to each for networks that are similar and far apart for networks that are dissimilar. This work presents a new descriptor based on the ideas from link analysis (e.g., HITS [4], PageRank [5]) to represent a network. These descriptors along with the more traditional descriptors such as number of nodes and number of edges are then used to model the accuracy of the network in Particle Swarm Optimization.

References

[1] Eberhart R. C. and Kennedy S., Proc. Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, pp. 39-43 (1995).

[2] Kennedy S., and Eberhart R.C., Swarm Intelligence, Morgan Kaufman, San Francisco (2001).

[3] Nikolova N., J. Jaworska. Approaches to Measure Chemical Similarity - a Review. QSAR Comb. Sci. 22, No. 9-10, 1006-1026 (2003)

[4] J. Kleinberg. Authoritative sources in a hyperlinked environment. In Proc. Ninth Ann. ACM-SIAM Symp. Discrete Algorithms, pages 668-677, ACM Press, New York, 1998

[5] Sergey Brin and Lawrence Page (1998). "The anatomy of a large-scale hypertextual Web search engine". Proceedings of the seventh international conference on World Wide Web 7: 107-117