Fundamental statistical features and self-similar properties of tagged networks

Abstract

We investigate the fundamental statistical features of tagged (or annotated) networks having a rich variety of attributes associated with their nodes. Tags (attributes, annotations, properties, features, etc.) provide essential information about the entity represented by a given node, thus, taking them into account represents a significant step towards a more complete description of the structure of large complex systems. Our main goal here is to uncover the relations between the statistical properties of the node tags and those of the graph topology. In order to better characterise the networks with tagged nodes, we introduce a number of new notions, including tag-assortativity (relating link probability to node similarity), and new quantities, such as node uniqueness (measuring how rarely the tags of a node occur in the network) and tag-assortativity exponent. We apply our approach to three large networks representing very different domains of complex systems. A number of the tag related quantities display analogous behaviour (e.g., the networks we studied are tag-assortative, indicating possible universal aspects of tags versus topology), while some other features, such as the distribution of the node uniqueness, show variability from network to network allowing for pin-pointing large scale specific features of real-world complex networks. We also find that for each network the topology and the tag distribution are scale invariant, and this self-similar property of the networks can be well characterised by the tag-assortativity exponent, which is specific to each system.

References in corpus (34)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Hierarchical organization of modularity in metabolic networks
• The large-scale organization of metabolic networks
• Evolutionary games on graphs
• Defining and identifying communities in networks
• Semantic Similarity in a Taxonomy: An Information-Based Measure and its Application to Problems of Ambiguity in Natural Language
• Detecting the overlapping and hierarchical community structure of complex networks
• Quantifying social group evolution
• Identity and Search in Social Networks
• Dynamics of market correlations: Taxonomy and portfolio analysis
• Nonequilibrium phase transition in the coevolution of networks and opinions
• Detecting fuzzy community structures in complex networks with a Potts model
• Phase diagrams for Prisoner's Dilemma game on two-dimensional lattices
• Coevolution of dynamical states and interactions in dynamic networks
• Cooperation in noisy case: prisoner's dilemma game on two types of regular random graphs
• Preferential attachment in the growth of social networks: the case of Wikipedia
• Generic Absorbing Transition in Coevolution Dynamics
• Consensus formation on adaptive networks
• Distance, dissimilarity index, and network community structure
• Cooperation and the Emergence of Role Differentiation in the Dynamics of Social Networks
• Wikipedias: Collaborative web-based encyclopedias as complex networks
• Coevolution of agents and networks: Opinion spreading and community disconnection
• Phenomenological Models of Socio-Economic Network Dynamics
• Time scale competition leading to fragmentation and recombination transitions in the coevolution of network and states
• Collaborative tagging as a tripartite network
• Spectral and network methods in the analysis of correlation matrices of stock returns
• Lack of consensus in social systems
• Taxonomy and clustering in collaborative systems: the case of the on-line encyclopedia Wikipedia
• On the Widespread Occurrence of the Inverse Square Distribution in Social Sciences and Taxonomy
• Quantifying the taxonomic diversity in real species communities

Cited by in corpus (25)

• Recommender Systems
• Finding overlapping communities in networks by label propagation
• Random hypergraphs and their applications
• Network Analysis of Particles and Grains
• Fuzzy overlapping communities in networks
• Global efficiency of local immunization on complex networks
• Hypergraph topological quantities for tagged social networks
• Hypergraph model of social tagging networks
• Intermittent social distancing strategy for epidemic control
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• I/O efficient bisimulation partitioning on very large directed acyclic graphs
• Percolation on random networks with arbitrary k-core structure
• Effect of degree correlations above the first shell on the percolation transition
• Growing networks of overlapping communities with internal structure
• Heterogeneous message passing for heterogeneous networks
• Self-organization in social tagging systems
• Parallel Maximum Clique Algorithms with Applications to Network Analysis and Storage
• What if CLIQUE were fast? Maximum Cliques in Information Networks and Strong Components in Temporal Networks
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• Ontologies and tag-statistics
• Statistical mechanics of ontology based annotations
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Representation of degree correlation using eigenvalue decomposition and its application to epidemic models
• Clustering of tag-induced sub-graphs in complex networks
• Ensemble-based Overlapping Community Detection using Disjoint Community Structures