Top

Published in:

2017 | OriginalPaper | Chapter

A Formal Concept Analysis Look at the Analysis of Affiliation Networks

Authors : Francisco J. Valverde-Albacete, Carmen Peláez-Moreno

Published in: Formal Concept Analysis of Social Networks

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

In this paper we try to analyse the dual-projection approach to weighted 2-mode networks using the tools of\(\mathcal{K}\)-Formal Concept Analysis (\(\mathcal{K}\)-FCA), an extension of FCA for incidences with values in a particular kind of semiring.

For this purpose, we first revisit the isomorphisms between 2-mode networks with formal contexts. In the quest for similar relations when the networks have non-Boolean weights, we relate the dual-projection method to both the Singular Value Decomposition and the Eigenvalue Problem of matrices with values in such algebras, as embodied in Kleinberg’s Hubs and Authorities (HITS) algorithm.

To recover a relation with multi-valued extensions of FCA, we introduce extensions of the HITS algorithm to calculate the influence of nodes in a network whose adjacency matrix takes values over dioids, zerosumfree semirings with a natural order. In this way, we show the original HITS algorithm to be a particular instance of the generic construction, but also the advantages of working in idempotent semifields, instances of dioids.

Subsequently, we also make some connections with extended\(\mathcal{K}\)-FCA, where the particular kind of dioid is an idempotent semifield, and provide theoretical reasoning and evidence that the type of knowledge extracted from a matrix by one procedure and the other are different.

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 Formal Concept Analysis of Attributed Networks

We will consider all graphs in this paper as directed graphs unless otherwise stated.

In [9] this is called “a fundamental pattern for the occurrence of lattices in general”; in [8] it is the “Basic Theorem of Concept Lattices”, and in Chap. 3 of [10] it is “the fundamental theorem of concept lattices”.

Birkhoff actually coined “crypto-isomorphism”, but the term seems to have been forced to evolve [12]. We point out that the “surprise” must come from finding concepts of different subfields to be the same. Of course cryptomorphisms boil down to plain isomorphisms as soon as the surprise fades away, so it is a mathematical concept more of an educational or sociological than a formal nature.

This procedure will be extended in Sect. 2.3.

To lessen the visual clutter, we drop the graph index from the matrix.

This term is not standard: for instance, [33] prefer to use “semiring with a multiplicative group structure”, but we prefer semifield to shorten out statements.

Bang-Jensen, J., Gutin, G.: Digraphs. Theory, Algorithms, and Applications, 3rd edn. Springer, Heidelberg (2001)

Agneessens, F., Everett, M.G.: Introduction to the special issue on advances in two-mode social networks. Soc. Netw. 35, 145–147 (2013)CrossRef

Latapy, M., Magnien, C., Vecchio, N.D.: Basic notions for the analysis of large two-mode networks. Soc. Netw. 30, 31–48 (2008)CrossRef

Everett, M.G., Borgatti, S.P.: The dual-projection approach for two-mode networks. Soc. Netw. 35, 204–210 (2013)CrossRef

Strang, G.: The fundamental theorem of linear algebra. Am. Math. Mon. 100, 848–855 (1993)MathSciNetCrossRef

Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. JHU Press, Baltimore (2012)MATH

Landauer, T.K., McNamara, D.S., Dennis, S., Kintsch, W.: Handbook of Latent Semantic Analysis. Lawrence Erlbaum Associates, Mahwah (2007)

Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer, Berlin/Heidelberg (1999)CrossRef

Wille, R.: Restructuring lattice theory: an approach based on hierarchies of concepts. In: Ordered Sets (Banff, Alta., 1981), pp. 445–470. Reidel, Boston (1982)CrossRef

10.

Davey, B., Priestley, H.: Introduction to Lattices and Order, 2nd edn. Cambridge University Press, Cambridge (2002)CrossRef

11.

Birkhoff, G.: Lattice Theory, 3rd edn. American Mathematical Society, Providence (1967)MATH

12.

Rota, G.C.: Indiscrete Thoughts. Springer, Boston, MA (2009)

13.

Freeman, L.C., White, D.R.: Using Galois lattices to represent network data. Sociol. Methodol. 23, 127–146 (1993)CrossRef

14.

Domenach, F.: CryptoLat - a pedagogical software on lattice cryptomorphisms and lattice properties. In: Ojeda-Aciego, M., Outrata, J. (eds.) 10th International Conference on Concept Lattices and Their Applications (2013)

15.

Gaume, B., Navarro, E., Prade, H.: A parallel between extended formal concept analysis and bipartite graphs analysis. In: IPMU’10: Proceedings of the Computational Intelligence for Knowledge-Based Systems Design, and 13th International Conference on Information Processing and Management of Uncertainty, Universite Paul Sabatier Toulouse III. Springer, Heidelberg (2010)CrossRef

16.

Kuznetsov, S.O.: Interpretation on graphs and complexity characteristics of a search for specific patterns. Nauchno-Tekhnicheskaya Informatsiya Seriya - Informationnye i sistemy 1, 23–27 (1989)

17.

Falzon, L.: Determining groups from the clique structure in large social networks. Soc. Netw. 22, 159–172 (2000)CrossRef

18.

Ali, S.S., Bentayeb, F., Missaoui, R., Boussaid, O.: An efficient method for community detection based on formal concept analysis. In: Foundations of Intelligent Systems, pp. 61–72. Springer, New York (2014)

19.

Roth, C., Bourgine, P.: Epistemic communities: description and hierarchic categorization. Math. Popul. Stud. 12 107–130 (2005)MathSciNetCrossRef

20.

Freeman, L.C.: Methods of social network visualization. In: Meyers, R.A. (ed.) Encyclopedia of Complexity and Systems Science, Entry 25, pp. 1–19. Springer, New York (2008)

21.

Duquenne, V.: On lattice approximations: syntactic aspects. Soc. Netw. 18, 189–199 (1996)CrossRef

22.

Bělohlávek, R., Vychodil, V.: Formal concepts as optimal factors in Boolean factor analysis: implications and experiments. In: Proceedings of the 5th International Conference on Concept Lattices and Their Applications, (CLA07), Montpellier, 24–26 October 2007

23.

Bělohlávek, R.: Fuzzy Relational Systems. Foundations and Principles. IFSR International Series on Systems Science and Engineering, vol. 20. Kluwer Academic, Norwell (2002)CrossRef

24.

Valverde-Albacete, F.J., Peláez-Moreno, C.: Extending conceptualisation modes for generalised Formal Concept Analysis. Inf. Sci. 181, 1888–1909 (2011)MathSciNetCrossRef

25.

Bělohlávek, R.: Optimal decompositions of matrices with entries from residuated lattices. J. Log. Comput. 22 (2012) 1405–1425MathSciNetCrossRef

26.

Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. J. ACM 46 (1999) 604–632MathSciNetCrossRef

27.

Easley, D.A., Kleinberg, J.M.: Networks, Crowds, and Markets - Reasoning About a Highly Connected World. Cambridge University Press, Cambridge (2010)CrossRef

28.

Kolaczyk, E.D., Csárdi, G.: Statistical Analysis of Network Data with R. Use R!, vol. 65. Springer, New York, NY (2014)MATH

29.

Lanczos, C.: Linear Differential Operators. Dover, New York (1997)MATH

30.

Golan, J.S.: Power Algebras over Semirings. With Applications in Mathematics and Computer Science. Mathematics and Its applications, vol. 488. Kluwer Academic, Dordrecht (1999)CrossRef

31.

Pouly, M., Kohlas, J.: Generic Inference. A Unifying Theory for Automated Reasoning. Wiley, Hoboken (2012)MATH

32.

Golan, J.S.: Semirings and Their Applications. Kluwer Academic, Dordrecht (1999)CrossRef

33.

Gondran, M., Minoux, M.: Graphs, Dioids and Semirings. New Models and Algorithms. Operations Research/Computer Science Interfaces. Springer, New York (2008)MATH

34.

Gondran, M., Minoux, M.: Valeurs propres et vecteurs propres dans les dioïdes et leur interprétation en théorie des graphes. EDF, Bulletin de la Direction des Etudes et Recherches, Serie C, Mathématiques Informatique 2, 25–41 (1977)

35.

Valverde-Albacete, F.J., Peláez-Moreno, C.: The spectra of irreducible matrices over completed idempotent semifields. Fuzzy Sets Syst. 271, 46–69 (2015)MathSciNetCrossRef

36.

Valverde-Albacete, F.J., Peláez-Moreno, C.: The spectra of reducible matrices over complete commutative idempotent semifields and their spectral lattices. Int. J. Gen. Syst. 45, 86–115 (2016)MathSciNetCrossRef

37.

Valverde-Albacete, F.J., Peláez-Moreno, C.: Spectral lattices of reducible matrices over completed idempotent semifields. In: Ojeda-Aciego, M., Outrata, J., (eds.) Concept Lattices and Applications (CLA 2013), pp. 211–224. Université de la Rochelle, Laboratory L31, La Rochelle (2013)

38.

Cohen, G., Gaubert, S., Quadrat, J.P.: Duality and separation theorems in idempotent semimodules. Linear Algebra Appl. 379, 395–422 (2004)MathSciNetCrossRef

39.

Peláez-Moreno, C., García-Moral, A.I., Valverde-Albacete, F.J.: Analyzing phonetic confusions using Formal Concept Analysis. J. Acoust. Soc. Am. 128, 1377–1390 (2010)CrossRef

40.

Valverde-Albacete, F.J., González-Calabozo, J.M., Peñas, A., Peláez-Moreno, C.: Supporting scientific knowledge discovery with extended, generalized formal concept analysis. Expert Syst. Appl. 44, 198–216 (2016)CrossRef

41.

González-Calabozo, J.M., Valverde-Albacete, F.J., Peláez-Moreno, C.: Interactive knowledge discovery and data mining on genomic expression data with numeric formal concept analysis. BMC Bioinf. 17, 374 (2016)CrossRef

42.

Valverde-Albacete, F.J., Peláez-Moreno, C.: The linear algebra in extended formal concept analysis over idempotent semifields. In: Bertet, K., Borchmann, D. (eds.) Formal Concept Analysis, Springer Berlin Heidelberg, 211–227 (2017)CrossRef

43.

Mirkin, B.: Mathematical Classification and Clustering. Nonconvex Optimization and Its Applications, vol. 11. Kluwer Academic, Dordrecht (1996)CrossRef

44.

Akian, M., Gaubert, S., Ninove, L.: Multiple equilibria of nonhomogeneous Markov chains and self-validating web rankings. arXiv:0712.0469 (2007)

Title: A Formal Concept Analysis Look at the Analysis of Affiliation Networks
Authors: Francisco J. Valverde-Albacete
Carmen Peláez-Moreno
Publisher: Springer International Publishing
Book: Formal Concept Analysis of Social Networks
Print ISBN: 978-3-319-64166-9

Electronic ISBN: 978-3-319-64167-6

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-64167-6_7

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner