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 (17)

• Uncovering the overlapping community structure of complex networks in nature and society
• Evolutionary games on graphs
• 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
• Nonequilibrium phase transition in the coevolution of networks and opinions
• 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
• 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
• 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
• Quantifying the taxonomic diversity in real species communities

Cited by in corpus (5)

• Random hypergraphs and their applications
• Self-organization in social tagging systems
• What if CLIQUE were fast? Maximum Cliques in Information Networks and Strong Components in Temporal Networks
• Clustering of tag-induced sub-graphs in complex networks
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks