Thesis etd-09232010-102536 |
Link copiato negli appunti
Thesis type
Tesi di laurea specialistica
Author
MAINARDI, SIMONE
URN
etd-09232010-102536
Thesis title
The Underlying Clustered Structure of Internet: A New Method to Efficiently Extract Communities
Department
INGEGNERIA
Course of study
INGEGNERIA INFORMATICA
Supervisors
relatore Prof. Lenzini, Luciano
relatore Prof. Mingozzi, Enzo
relatore Ing. Gardellin, Vanessa
relatore Prof. Mingozzi, Enzo
relatore Ing. Gardellin, Vanessa
Keywords
- autonomous system
- clusters
- communities
- community extraction algorithm
- community extraction method
- Internet
Graduation session start date
14/10/2010
Availability
Withheld
Release date
14/10/2050
Summary
Uncovering the underlying clustered structure of Internet is essential to unveil insights into its functional organization. This thesis is focused on discovering such clustered structure in terms of the building blocks it is composed of, building blocks ofter referred to as communities. There have been proposed several definitions of community in the literature and in this work we will try to present some of the most studied and widely used, discussing about their characteristics and properties. Among these definitions, the k-clique community has seemed us the most significant in catching the characteristics cohese groups shoud have. The reasons have driven us to focus on such definition of community will be extensively discussed.
Extracting k-clique communities requires a substantial amount of computational load at least for real-world datasets. At the best of our knowledge, no existing software tool has been able to extract these communities from the Internet at the Autonomous System level of abstraction and this has encouraged us in developing a new parallel method that could extract communities efficiently by exploiting a parallel shared memory computing architecture togheter with particular data structures known as disjoint-set data structures. In this thesis the new method will be presented and discussed and experimental results showing the efficiency and the effectivity of this method in extracting communities will be exposed. This work will be concluded with the analysis of the structural properties of the Interent in terms of communities and interconnections between them using both sigle- and multi-criterion scores as meters of the quality of such extracted clusters.
Extracting k-clique communities requires a substantial amount of computational load at least for real-world datasets. At the best of our knowledge, no existing software tool has been able to extract these communities from the Internet at the Autonomous System level of abstraction and this has encouraged us in developing a new parallel method that could extract communities efficiently by exploiting a parallel shared memory computing architecture togheter with particular data structures known as disjoint-set data structures. In this thesis the new method will be presented and discussed and experimental results showing the efficiency and the effectivity of this method in extracting communities will be exposed. This work will be concluded with the analysis of the structural properties of the Interent in terms of communities and interconnections between them using both sigle- and multi-criterion scores as meters of the quality of such extracted clusters.
File
Nome file | Dimensione |
---|---|
The thesis is not available. |