Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Entropy of Digraphs and Infinite Networks Read chapter Read first chapter

2011 | OriginalPaper | Chapter

10. Social Ontologies as Generalized Nearly Acyclic Directed Graphs: A Quantitative Graph Model of Social Tagging

Author : Alexander Mehler

Published in: Towards an Information Theory of Complex Networks

Publisher: Birkhäuser Boston

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we introduce a quantitative graph model of social ontologies as exemplified by the category system of Wikipedia. This is done to contrast structure formation in distributed cognition with classification schemes (by example of the DDC and MeSH), formal ontologies (by example of OpenCyc and SUMO), and terminological ontologies (as exemplified by WordNet). Our basic findings are that social ontologies have a characteristic topology that clearly separates them from other types of ontologies. In this context, we introduce the notion of a Zipfian bipartivity to analyze the relationship of categories and categorized units in distributed cognition.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Markov Entropy Centrality: Chemical, Biological, Crime, and Legislative Networks
next chapter Typology by Means of Language Networks: Applying Information Theoretic Measures to Morphological Derivation Networks
Footnotes
1
Note that within the social ontologies analyzed here, i.e. Wikipedia category systems, moderation may occur.
 
2
Such links are anchored within the body of an article, but not at the end of it where categorization links are located.
 
3
The order of a graph equals the number of its vertices [32].
 
4
Note that the documentation of the Wikipedia suggests the absence of cycles and that the category system of the Wikipedia spans DAGs (cf. http://​en.​wikipedia.​org/​wiki/​Wikipedia:​Categorization). We show more precisely the degree by which this is only approximately true.
 
5
This approach is in the line of [13] who develops information-theoretic indices of graphs and their topology. See also [87] for a related approach in the area of quantitative biology. A second impulse comes from [22] who calculates entropies of probability distributions of vertices in complex networks. Albeit this coincidence we deal with complex nearly DAG-like graphs apart from complex networks. In any event, it is our conviction that the analysis of graph structures can gain invaluable insights from these two approaches beyond of what has been done so far in complex network theory.
 
6
Note that the graphs in Fig. 10.5 denote different scenarios only schematically.
 
7
Note that we use the terms index and measure synonymously (cf. [41]).
 
8
Of course, every weakly connected component of the [ ]-variant of the SOC has at least one source. This information is already implicity explored by means of the connected component statistics. Thus, we focus on operating on the LCC of each SOG when calculating the multiplicity index.
 
9
Note that μ = . 514 and σ = . 3621.
 
10
This also means that if we disregard the multiplicity of sources we may say that SOGs tend to be tree-like.
 
11
By D − u we denote in the usual way the subdigraph of D induced by V ∖ { u}.
 
12
Note that [85] as well as [76] and [77] aim at improving shortest path algorithms by operating on nearly acyclic graphs but not on graph classification. Therefore, the deficiency we found is irrelevant for them.
 
13
At this point one might ask why we do not use a simpler notion of cyclicity [38] by counting, for example, the number of edges to be deleted in order to make a graph acyclic? The simple reason is that index (10.10) is more informative about the DAG-like structure of a SOG as it additionally includes the impact of multiple sources.
 
14
A synergetic model [2, 39] of this process could be a starting point to build an integrative model of all characteristics of structure formation considered here. However, at present this is out of reach.
 
15
At this point, we might also take the variance or mean of the feature vector q(x) as an aggregation function to measure the balance of x. See [52, 70] for such an approach.
 
16
Note that this main category is always unique.
 
17
An obvious alternative to this approach would be to analyze the distribution of imbalance values in a SOG – this will be one reference point for future work.
 
18
Botafogo et al. [14] already utilized depth as a reference quantity of imbalance. However, they unnecessarily use a recursive function for defining it and miss demonstrating its empirical significance.
 
19
Without following this line of research here, it may be interesting to consider this level of maximum order from the point of view of conceptual levels in prototype theory [74].
 
20
See [54] who have introduced this notion in the area of modeling web genres.
 
24
Thus, the reader should not confuse ℂ r with a random uniform distribution of the objects over the target classes.
 
25
In Table 10.9 we present the F-score of the best performing subset of features. This subset is reported in the 6th column of Fig. 10.22. We see that, by representing the target ontologies by this feature subset, the F-score is raised. Below we discuss this result in the context of testing the OSH.
 
Literature
1.
Altmann, G.: Semantische Diversifikation. Folia Ling. 19, 177–200 (1985)
2.
Altmann, G., Köhler, R.: “Language forces” and synergetic modelling of language phenomena. In: Glottometrika, vil. 15, pp. 62–76. Brockmeyer, Bochum (1996)
3.
Altmann, G., Lehfeldt. W.: Allgemeine Sprachtypologie. Fink, München (1973)
4.
Baldi, P., Frasconi, P., Smyth, P.: Modeling the Internet and the Web. Wiley, Chichester (2003)
5.
Bales, M.E., Lussier, Y.A., Johnson, S.B.: Topological analysis of large-scale biomedical terminology structures. J. Am. Med. Informat. Assoc. 14(6), 788–797 (2007)CrossRef
6.
Bang-Jensen, J., Gutin, G.: Digraphs. Theory, Algorithms and Applications. Springer, London/Berlin (2006)
7.
8.
Barrat, A., Barthélemy, M., Vespignani, A.: Dynamical Processes on Complex Networks. Cambridge University Press, Cambridge (2008)CrossRefMATH
9.
Barthélemy, M.: Betweenness centrality in large complex networks. Eur. Phys. J. B 38, 163–168 (2004)CrossRef
10.
Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S.: DAG-width and parity games. In: Durand, B., Thomas, W. (eds.) STACS, vol. 3884, Lecture Notes in Computer Science, pp. 524–536. Springer, Berlin (2006)
11.
Bickhard, M.H.: Social ontology as convention. Topoi 27(1-2), 139–149 (2008)CrossRef
12.
Blohm, S., Kroetzsch, M., Cimiano, P.: Integrating the fast and the numerous – combining machine and community intelligence for semantic annotation and Wikipedia: Folksonomy meets rigorously defined common-sense. In: Proceedings of AAAI 2008 Workshop on Wikipedia and Artificial Intelligence: An Evolving Synergy (WikiAI08), Chicago (2008)
13.
Bonchev, D.: Information Theoretic Indices for Characterization of Chemical Structures. Research Studies Press, Chichester (1983)
14.
Botafogo, R.A., Rivlin, E., Shneiderman, B.: Structural analysis of hypertexts: Identifying hierarchies and useful metrics. ACM Trans. Inform. Syst. 10(2), 142–180 (1992)CrossRef
15.
Budanitsky, A., Hirst, G.: Evaluating WordNet-based measures of lexical semantic relatedness. Comput. Ling. 32(1), 13–47 (2006)CrossRefMATH
16.
Caldarelli, G.: Scale-Free Networks. Complex webs in nature and technology. Oxford University Press, Oxford (2008)MATH
17.
Capocci, A., Caldarelli, G.: Folksonomies and clustering in the collaborative system CiteULike. J. Phys. A Math. Theor. 41, 224016 (2008)CrossRefMathSciNet
18.
Capocci, A., Rao, F., Caldarelli, G.: Taxonomy and clustering in collaborative systems: the case of the on-line encyclopedia Wikipedia. Europhys. Lett. 81, 28006 (2008)CrossRef
19.
Cattuto, C., Barrat, A., Baldassarri, A., Schehr, G., Loreto, V.: Collective dynamics of social annotation. PNAS 106(26), 10511–10515 (2009)
20.
Cattuto, C., Benz, D., Hotho, A., Stumme, G.: Semantic grounding of tag relatedness in social bookmarking systems. In: The Semantic Web – ISWC 2008, vol. 5318, Lecture Notes in Computer Science, pp. 615–631. Springer, Berlin, Heidelberg (2008)
21.
Chernov, S., Iofciu, T., Nejdl, W., Zhou, X.: Extracting semantic relationships between Wikipedia categories. In: 1st International Workshop: From Wiki to Semantics (Sem Wiki 2006), co-located with ESWC 2006, Budva, Montenegro, June 12, 2006
22.
Dehmer, M.: Information processing in complex networks: Graph entropy and information functionals. Appl. Math. Comput. 201, 82–94 (2008)MathSciNetMATH
23.
Dehmer, M., Mehler, A.: A new method of measuring the similarity for a special class of directed graphs. Tatra Mountains Math. Publ. 36, 39–59 (2007)MathSciNetMATH
24.
25.
Dellschaft, K., Staab, S.: An epistemic dynamic model for tagging systems. In: Hypertext 2008, Proceedings of the 19th ACM Conference on Hypertext and Hypermedia, June 19–21, 2008, Pittsburgh, Pennsylvania, USA, 2008
26.
Estrada, E.: Protein bipartivity and essentiality in the yeast protein-protein interaction network. J. Proteome Res. 5(9), 2177–2184 (2006)CrossRef
27.
Estrada, E., Rodríguez-Velázquez, J.A.: Spectral measures of bipartivity in complex networks. Phys. Rev. E 72(4), 046105 (2005)CrossRefMathSciNet
28.
Fellbaum, C., (ed.): WordNet: An Electronic Lexical Database. MIT Press, Cambridge (1998)MATH
29.
Firth, J.R.: A synopsis of linguistic theory, 1933–1955. In: Firth, J.R., (ed.) Studies in Linguistic Analysis, pp. 1–32. Blackwell, Oxford (1957)
30.
Freyd, J.J.: Shareability: The social psychology of epistemology. Cognit. Sci. 7, 191–210 (1983)CrossRef
31.
Hammwöhner, R.: Interlingual aspects of Wikipedia’s quality. In: Proceedings of the International Conference On Information Qualiy (ICIQ 2007) (2007)
32.
33.
Hollan, J., Hutchins, E., Kirsh, D.: Distributed cognition: toward a new foundation for human-computer interaction research. ACM Trans. Comput. Hum. Interact. 7(2), 174–196 (2000)CrossRef
34.
Holme, P., Liljeros, F., Edling, C.R., Kim, B.J.: On network bipartivity. Phys. Rev. E 68, 056107 (2003)CrossRef
35.
Hotho, A., Jäschke, R., Schmitz, C., Stumme, G.: BibSonomy: A social book-mark and publication sharing system. In: Proceedings Of the Workshop on Tool Interoperability at the International Conference on Conceptual Structures 2006, pp. 87–102 (2006)
36.
Hotho, A., Nürnberger, A., Paaß, G.: A brief survey of text mining. J. Lang. Tech. Comput. Ling. 20(1), 19–62 (2005)
37.
Jäschke, R., Hotho, A., Schmitz, C., Ganter, B., Stumme, G.: Discovering shared conceptualizations in folksonomies. Web Semant. Sci. Serv. Agents World Wide Web 6(1), 38–53 (2008)CrossRef
38.
39.
Köhler, R.: Systems theoretical linguistics. Theor. Ling. 14(2/3), 241–257 (1987)
40.
Köhler, R.: Syntactic structures, properties and interrelations. J. Quant. Ling. 6, 46–57 (1999)CrossRef
41.
Koschützki, D., Lehmann, K.A., Peeters, L., Richter, S., Tenfelde-Podehl, D., Zlotowski, O.: Centrality indices. In: Brandes, U., Erlebach, T., (eds.) Network Analysis, vol. 3418, Lecture Notes in Computer Science, pp. 16–61. Springer, Berlin (2004)
42.
Kunze, C., Lemnitzer, L.: GermaNet – representation, visualization, application. In Rodriguez, M., González, Paz Suárez Araujo, C., (eds.) Proceedings of the 3rd International Conference on Language Resources and Evaluation (LREC 2002), pp. 1485–1491. European Language Resources Association, Paris (2002)
43.
Lambiotte, R., Ausloos, M.: Collaborative tagging as a tripartite network. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J., (eds.) International Conference on Computational Science (3), vol. 3993, Lecture Notes in Computer Science, pp. 1114–1117. Springer, Berlin (2006)
44.
Lenat, D.B.: CYC: A large-scale investment in knowledge infrastructure. Comm. ACM 38, 33–38 (1995)CrossRef
45.
Medelyan, O., Witten, I.H., Milne, D.: Topic indexing with Wikipedia. In: Proceedings of AAAI 2008 Workshop on Wikipedia and Artificial Intelligence: An Evolving Synergy (WikiAI08), Chicago (2008)
46.
Mehler, A.: Text linkage in the wiki medium – a comparative study. In: Karlgren, J., (ed.) Proceedings of the EACL Workshop on New Text – Wikis and blogs and other dynamic text sources, pp. 1–8. Trento, Italy (2006)
47.
Mehler, A.: Large text networks as an object of corpus linguistic studies. In: Lüdeling, A., Kytö, M., (eds.) Corpus Linguistics. An International Handbook of the Science of Language and Society, pp. 328–382. De Gruyter, Berlin/NewYork (2008)
48.
Mehler, A.: On the impact of community structure on self-organizing lexical networks. In: Smith, A.D.M., Smith, K., Ferrer i Cancho, R., (eds.) Proceedings of the 7th Evolution of Language Conference (Evolang7), pp. 227–234. World Scientific, Barcelona (2008)
49.
Mehler, A.: Structural similarities of complex networks: A computational model by example of wiki graphs. Appl. Artif. Intell. 22(7&8), 619–683 (2008)CrossRef
50.
Mehler, A.: Generalized shortest paths trees: A novel graph class applied to semiotic networks. In: Dehmer, M., Emmert-Streib, F., (eds.) Analysis of Complex Networks: From Biology to Linguistics, pp. 175–220. Wiley-VCH, Weinheim (2009)CrossRefMATH
51.
Mehler, A.: Minimum spanning Markovian trees: Introducing context-sensitivity into the generation of spanning trees. In: Dehmer, M., (ed.) Structural Analysis of Complex Networks, pp. 381–401. Birkhäuser/Basel (2010)
52.
Mehler, A., Geibel, P., Pustylnikov, O.: Structural classifiers of text types: Towards a novel model of text representation. J. Lang. Tech. Comput. Ling. 22(2), 51–66 (2007)
53.
Mehler, A., Gleim, R., Ernst, A., Waltinger, U.: WikiDB: Building interoperable wiki-based knowledge resources for semantic databases. Sprache und Datenverarbeitung Int. J. Lang. Data Process. 32(1), 47–70 (2008)
54.
Mehler, A., Gleim, R., Wegner, A.: Structural uncertainty of hypertext types. An empirical study. In: Proceedings of the Workshop “Towards Genre-Enabled Search Engines: The Impact of NLP”, in conjunction with RANLP 2007, pp. 13–19. Borovets, Bulgaria (2007)
55.
Meluk, I.: Dependency Syntax: Theory and Practice. SUNY, Albany (1988)
56.
Mika, P.: Ontologies are us: A unified model of social networks and semantics. J. Web Semant. 5(1), 5–15 (2007)CrossRef
57.
Mika, P., Gangemi, A.: Descriptions of social relations. In: Proceedings of the 1st Workshop on Friend of a Friend, Social Networking and the (Semantic) Web (2004)
58.
Milne, D., Witten, I.H.: An effective, low-cost measure of semantic relatedness obtained from Wikipedia links. In: Proceedings of AAAI 2008 Workshop on Wikipedia and Artificial Intelligence: An Evolving Synergy (WikiAI08), Chicago (2008)
59.
Naranan, S., Balasubrahmanyan, V.K.: Models for power law relations in linguistics and information science. J. Quant. Ling. 5(1-2), 35–61 (1998)CrossRef
60.
Nelson, S.J., Johnston, W.D., Humphreys, B.L.: Relationships in medical subject headings. In: Bean, C.A., Green, R., (eds.) Relationships in the organization of knowledge, pp. 171–184. Kluwer Academic Publishers, New York (2001)CrossRef
61.
62.
Newman, M.E.J.: Power laws, Pareto distributions and Zipf’s law. Contemp. Phys. 46, 323–351 (2005)
63.
Newman, M.E.J., Park, J.: The origin of degree correlations in the internet and other networks. Phys. Rev. E 68, 026121 (2003)CrossRef
64.
Niles, I., Pease, A.: Towards a standard upper ontology. In: Welty, C., Smith, B., (eds.) Proceedings of the 2nd International Conference on Formal Ontology in Information Systems (FOIS-2001), Ogunquit, Maine (2001)
65.
Obdržálek, J.: DAG-width: connectivity measure for directed graphs. In: SODA’06: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 814–821. ACM, New York, NY, USA (2006)
66.
67.
68.
Pastor-Satorras, R., Vázquez, A., Vesipignani, A.: Dynamical and correlation properties of the internet. Phys. Rev. Letters 87(25), 268701 (2001)CrossRef
69.
Ponzetto, S., Strube, M.: Deriving a large scale taxonomy from Wikipedia. In: Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI-07), pp. 1440–1447. Vancouver, B.C., Canada (2007)
70.
Pustylnikov, O., Mehler, A.: Structural differentiate of text types. A quantitative model. In: Proceedings of the 31st Annual Conference of the German Classification Society on Data Analysis, Machine Learning, and Applications (GfKl), pp. 655–662 (2007)
71.
Pustylnikov, O., Mehler, A.: Text classification by means of structural features. What kind of information about texts is captured by their structure? In: Proceedings of RUSSIR’08. Taganrog, Russia (2008)
72.
Abramov, O., Mehler, A.: Automatic language classification by means of syntactic dependency networks. J. Quant. Ling. (2011) (accepted)CrossRef
73.
Ravasz, E., Barabási, A.-L.: Hierarchical organization in complex networks. Phys. Rev. E 67, 026112 (2003)CrossRefMATH
74.
Rosch, E.: Principles of categorization. In: Rosch, E., Lloyd, B.B., (eds.) Cognition and Categorization, pp. 27–48. Erlbaum, Hillsdale, N.J. (1978)
75.
Santini, M.: Characterizing genres of web pages: Genre hybridism and individualization. In: Proceedings of the 40th Annual Hawaii International Conference on System Sciences (HICSS’07) (2007)
76.
Saunders, S.: Improved shortest path algorithms for nearly acyclic graphs. Ph.D thesis, University of Canterbury, Computer Science (2004)
77.
Saunders, S., Takaoka, T.: Improved shortest path algorithms for nearly acyclic graphs. Theor. Comput. Sci. 293(3), 535–556 (2003)CrossRefMathSciNetMATH
78.
Saunders, S., Takaoka, T.: Solving shortest paths efficiently on nearly acyclic directed graphs. Theor. Comput. Sci. 370(1-3), 94–109 (2007)CrossRefMathSciNetMATH
79.
Searle, J.R.: Social ontology. Some basic principles. Anthropol. Theor. 6(1), 12–29 (2006)CrossRef
80.
Skorobogatov, V.A., Dobrynin, A.A.: Metrical analysis of graphs. MATCH 23, 105–155 (1988)
81.
Sowa, J.F.: Knowledge Representation: Logical, Philosophical, and Computational Foundations. Brooks/Cole, Pacific Grove (2000)
82.
Steels, L.: Collaborative tagging as distributed cognition. Pragmatics Cognit. 14(2), 287–292 (2006)CrossRef
83.
Steyvers, M., Tenenbaum, J.: The large-scale structure of semantic networks: Statistical analyses and a model of semantic growth. Cognit. Sci. 29(1), 41–78 (2005)CrossRef
84.
Suchanek, F.M., Kasneci, G., Weikum, G.: Yago: a core of semantic knowledge. In: WWW’07: Proceedings of the 16th international conference on World Wide Web, pp. 697–706. ACM, New York, NY, USA (2007)
85.
86.
Tuldava, J.: Probleme und Methoden der quantitativ-systemischen Lexikologie. Wissenschaftlicher Verlag, Trier (1998)
87.
Ulanowicz, R.E.: Identifying the structure of cycling in ecosystems. Math. Biosci. 65(2), 219–237 (1983)CrossRefMATH
88.
Voss, J.: Collaborative thesaurus tagging the Wikipedia way. arXiv.org:cs/0604036 (2006)
89.
Waltinger, U., Mehler, A., Heyer, G.: Towards automatic content tagging: Enhanced web services in digital libraries using lexical chaining. In: Cordeiro, J., Filipe, J., Hammoudi, S., (eds.) 4th Int. Conf. on Web Information Systems and Technologies (WEBIST ’08), pp. 231–236. INSTICC Press, Barcelona, Funchal, Portugal (2008)
90.
Watts, D.J.: Six Degrees. The Science of a Connected Age. W. W. Norton & Company, New York/London (2003)
91.
92.
Zipf, G.K.: Human Behavior and the Principle of Least Effort. An Introduction to Human Ecology. Hafner Publishing Company, New York (1972)
93.
Zlatic, V., Bozicevic, M., Stefancic, H., Domazet, M.: Wikipedias: Collaborative web-based encyclopedias as complex networks. Phys. Rev. E 74, 016115 (2006)CrossRef
Metadata
Title
Social Ontologies as Generalized Nearly Acyclic Directed Graphs: A Quantitative Graph Model of Social Tagging
Author
Alexander Mehler
Copyright Year
2011
Publisher
Birkhäuser Boston
Book
Towards an Information Theory of Complex Networks

Print ISBN: 978-0-8176-4903-6

Electronic ISBN: 978-0-8176-4904-3

Copyright Year: 2011

DOI
https://doi.org/10.1007/978-0-8176-4904-3_10

Premium Partner

    Image Credits