Online Social Networks (OSN) during last years acquired a huge and increasing popularity as one of the most important emerging Web phenomena, deeply modifying the behavior of users and contributing to build a solid substrate of connections and relationships among people using the Web. In this preliminary work paper, our purpose is to analyze Facebook, considering a signi�cant sample of data re ecting relationships among subscribed users. Our goal is to extract, from this platform, relevant information about the distribution of these relations and exploit tools and algorithms provided by the Social Network Analysis (SNA) to discover and, possibly, understand underlying similarities between the developing of OSN and real-life social networks.
A common SNA task is to discover, if existing, aggregations and subsets of nodes playing similar roles or occupying a particular position in a network @cite_11 . Some strictly connected problems are related to optimizing the visual representation of graphs @cite_21 ; for large social networks graphs is not trivial to find a meaningful graphical representation, because of the number of elements to display, and finding algorithms for the planar embedding of the graph, so as reducing (or eliminating) intersecting edges and improving aesthetic and functional characteristics of the graph itself, is part of the solution @cite_17 .
@cite_21 @cite_17 @cite_11
1992709202 2121655825 1554338108
Several data presentation problems involve drawing graphs so that they are easy to read and understand. Examples include circuit schematics and diagrams for information systems analysis and design. In this paper we present a bibliographic survey on algorithms whose goal is to produce aesthetically pleasing drawings of graphs. Research on this topic is spread over the broad spectrum of computer science. This bibliography constitutes a first attempt to encompass both theoretical and application-oriented papers from disparate areas. We present new O(n)-time methods for planar embedding and Kuratowski subgraph isolation that were inspired by the Booth-Lueker PQ-tree implementation of the Lempel-Even-Cederbaum vertex addition method. In this paper, we improve upon our conference proceedings formulation and upon the Shih-Hsu PC-tree, both of which perform comprehensive tests of planarity conditions embedding the edges from a vertex to its descendants in a ‘batch’ vertex addition operation. These tests are simpler than but analogous to the templating scheme of the PQ-tree. Instead, we take the edge to be the fundamental unit of addition to the partial embedding while preserving planarity. This eliminates the batch planarity condition testing in favor of a few localized decisions of a path traversal process, and it exploits the fact that subgraphs can become biconnected by adding a single edge. Our method is presented using only graph constructs, but our definition of external activity, path traversal process and theoretical analysis of correctness can be applied to optimize the PC-tree Acknowledgements 1. Introduction Stanley Wasserman, John Scott and Peter J. Carrington 2. Recent developments in network measurement Peter V. Marsden 3. Network sampling and model fitting Ove Frank 4. Extending centrality Martin Everett and Stephen P. Borgatti 5. Positional analyses of sociometric data Patrick Doreian, Vladimir Batagelj and Anuska Ferligoj 6. Network models and methods for studying the diffusion of innovations Thomas W. Valente 7. Using correspondence analysis for joint displays of affiliation networks Katherine Faust 8. An introduction to random graphs, dependence graphs, and p* Stanley Wasserman and Garry Robins 9. Random graph models for social networks: multiple relations or multiple raters Laura M. Koehly and Philippa Pattison 10. Interdependencies and social processes: dependence graphs and generalized dependence structures Garry Robins and Philippa Pattison 11. Models for longitudinal network data Tom A. B. Snijders 12. Graphical techniques for exploring social network data Linton C. Freeman 13. Software for social network analysis Mark Huisman and Marijtje A. J. van Duijn Index.