A measure for cluster cohesion in semantic overlay networks

ABSTRACT

Semantic overlay networks cluster peers that are semantically, thematically or socially close into groups by means of a rewiring procedure that is periodically executed by each peer. Rewiring proceeds by establishing new connections to similar peers, and by discarding connections that are outdated or pointing to dissimilar peers. This process aims at improving cluster quality (how well peers with similar content are clustered together) and by this, at improving the flow of information in the network by reducing the number of messages that are exchanged. Therefore, measuring the quality of clustering is an important issue by itself. This is exactly the issue this work is dealing with. In this paper, we introduce a new clustering measure that takes into account the whole neighborhood of a peer (rather than its direct neighbors) thus, providing better insight on the quality of the underlying clustered organisation. Our experimental evaluation with real-word data and queries confirms our assumption that the new measure is better suited for measuring clustering quality than other known measures, such as the (generalised) clustering coefficient.

REFERENCES

• 1: Engineering graph clustering: Models and experimental evaluation, Journal of Experimental Algorithmics (JEA), 12, June 2008 [doi>10.1145/1227161.1227162]
• 2: C. Doulkeridis, K. Noervaag, and M. Vazirgiannis. Scalable Semantic Overlay Generation for P2P-based Digital Libraries. In ECDL, 2006.
• 3: Bertalan Forstner , Hassan Charaf, Analytical model for semantic overlay networks in peer-to-peer systems, Proceedings of the 5th WSEAS International Conference on Software Engineering, Parallel and Distributed Systems, p.82-87, February 15-17, 2006, Madrid, Spain
• 4: A. Fronczak, J.A. HoImage, M. Jedynak, and J. Sienkiewicz. Higher Order Clustering Coefficients in Barabasi-Albert Networks. Physica A: Statistical Mechanics and its Applications, 316(1--4), 2002.
• 5: H. Garcia-Molina and B. Yang. Efficient Search in Peer-to-Peer Networks. In ICDCS, 2002.
• 6: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 7: H.F. Hansen, C.A. Andresen, and A. Hansen. A Quantitative Measure for Path Structures of Complex Networks. EPL: A Letters Journal Exploring the Frontiers of Physics, 78, May 2007.
• 8: Ken Y. K. Hui , John C. S. Lui , David K. Y. Yau, Small-world overlay P2P networks: construction, management and handling of dynamic flash crowds, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.15, p.2727-2746, 18 October 2006 [doi>10.1016/j.comnet.2005.10.010]
• 9: Iraklis A. Klampanos , Joemon M. Jose, An architecture for information retrieval over semi-collaborating Peer-to-Peer networks, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968119]
• 10: G. Koloniari and E. Pitoura. Recall-based Cluster Reformulation by Selfish Peers. In NetDB, 2008.
• 11: Mei Li , Wang-Chien Lee , Anand Sivasubramaniam, Semantic Small World: An Overlay Network for Peer-to-Peer Search, Proceedings of the 12th IEEE International Conference on Network Protocols, p.228-238, October 05-08, 2004
• 12: A. Linari and M. Patella. Metric Overlay Networks: Processing Similarity Queries in P2P Databases. In DBISP2P, 2007.
• 13: A. Loser and C. Tempich. On Ranking Peers in Semantic Overlay Networks. In WM, 2005.
• 14: A. Loser, M. Wolpers, W. Siberski, and W. Nejdl. Semantic Overlay Clusters within Super-Peer Networks. In DBISP2P, 2003.
• 15: Jie Lu , Jamie Callan, Content-based retrieval in hybrid peer-to-peer networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956903]
• 16: Wolfgang Nejdl , Boris Wolf , Changtao Qu , Stefan Decker , Michael Sintek , Ambjörn Naeve , Mikael Nilsson , Matthias Palmér , Tore Risch, EDUTELLA: a P2P networking infrastructure based on RDF, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511525]
• 17: C. H. Ng, K. C. Sia, and C. H. Chang. Advanced Peer Clustering and Firework Query Model in the Peer-to-Peer Network. In WWW, 2002.
• 18: Josiane Xavier Parreira , Sebastian Michel , Gerhard Weikum, p2pDating: Real life inspired semantic overlay networks for Web search, Information Processing and Management: an International Journal, v.43 n.3, p.643-664, May, 2007 [doi>10.1016/j.ipm.2006.09.007]
• 19: Paraskevi Raftopoulou , Euripides G. Petrakis , Christos Tryfonopoulos , Gerhard Weikum, Information Retrieval and Filtering over Self-organising Digital Libraries, Proceedings of the 12th European conference on Research and Advanced Technology for Digital Libraries, September 14-19, 2008, Aarhus, Denmark [doi>10.1007/978-3-540-87599-4_34]
• 20: P. Raftopoulou and E.G.M. Petrakis. iCluster: a Self-Organising Overlay Network for P2P Information Retrieval. In ECIR, 2008.
• 21: Matthew J. Rattigan , Marc Maier , David Jensen, Graph clustering with network structure indices, Proceedings of the 24th international conference on Machine learning, p.783-790, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273595]
• 22: J. Sacha, J. Dowling, R. Cunningham, and R. Meier. Discovery of Stable Peers in a Self-organising Peer-to-Peer Gradient Topology. In DAIS, 2006.
• 23: C. Schmitz. Self-Organization of a Small World by Topic. In P2PKM, 2004.
• 24: J. Sedmidubsky, S. Barton, V. Dohnal, and P. Zezula. Adaptive Approximate Similarity Searching through Metric Social Networks. In ICDE, 2008.
• 25: K. Spripanidkulchai, B. Maggs, and H. Zhang. Efficient Content Location using Interest-Based Locality in Peer-to-Peer Systems. In INFOCOM, 2003.
• 26: Chunqiang Tang , Zhichen Xu , Sandhya Dwarkadas, Peer-to-peer information retrieval using self-organizing semantic overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863976]
• 27: P. Triantafillou, C. Xiruhaki, M. Koubarakis, and N. Ntarmos. Towards High Performance Peer-to-Peer Content and Resource Sharing Systems. In CIDR, 2003.
• 28: Duncan J. Watts, Small worlds: the dynamics of networks between order and randomness, Princeton University Press, Princeton, NJ, 1999
• 29: D. J. Watts and S. H. Strogatz. Collective Dynamics of 'Small-World' Networks. Nature, 393, 1998.
• 30: Jinxi Xu , W. Bruce Croft, Cluster-based language models for distributed retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.254-261, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312687]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Experimentation, Measurement

Keywords:
clustering measure, information retrieval, semantic overlay networks