Abstract patterns and sub-communities in attributed graphs

Abstract patterns and sub-communities in attributed graphs

Henry SoldanoGuillaume Santini Dominique Bouthinon 

Université Paris 13, Sorbonne Paris Cité, L.I.P.N., UMR-CNRS 7030, Villetaneuse, F-93430, France

Museum National d'Histoire Naturelle, ABI, ISYEB, UMR 7205, CNRS MNHN UPMC EPHE, Paris, F-75005, France

Corresponding Author Email: 
henry.soldano,guillaume.santini,db@lipn.univ-paris13.fr, henry.soldano@mnhn.fr
Page: 
441-468
|
DOI: 
https://doi.org/10.3166/RIA.30.441-468
Received: 
N/A
| |
Accepted: 
N/A
| | Citation
Abstract: 

We consider attribute pattern mining in an attributed graph through recent developments of Formal Concept Analysis. The core idea is to restrain the extensional space; i.e. the space of possible pattern extensions in the vertex set O, to vertex subsets satisfying structural properties. We consider two levels. At the global level, we reduce the extension of each pattern in such a way that the corresponding abstract extension induces a subgraph whose nodes satisfy some connectivity property. At the local level a pattern has various extensions each associated to a connected component of the abstract subgraph associated to the pattern. We obtain that way abstract closed patterns and local closed patterns, together with abstract and local implication rules. We consider in particular the detection and ordering of κ-communities in subgraphs of an attributed network.

Keywords: 

attributed networks, closed pattern mining, formal concept analysis

1. Introduction
2. Jeux de données
3. Motifs fermés abstraits dans les graphes attribués
4. Motifs fermés locaur
5. Ce-confluences dans un graphe dérivé
6. Implementation
7. Conclusion
  References

Balasundaram B., Butenko S., Trukhanov S. (2005). Novel approaches for analyzing biological networks. Journal of Combinatorial Optimization, vol. 10, no 1, p. 23–39.

Barabàsi A.-L., Albert R. (1999). Emergence of scaling in random networks. Science, vol. 286, no 5439, p. 509-512.

Batagelj V., Zaversnik M. (2011). Fast algorithms for determining (generalized) core groups in social networks. Adv. Data Analysis and Classification, vol. 5, no 2, p. 129–145.

Bechara Prado A., Plantevit M., Robardet C., Boulicaut J.-F. (2013). Mining Graph Topological Patterns: Finding Co-variations among Vertex Descriptors. IEEE Transactions on Knowledge and Data Engineering, vol. 25, no 9, p. 2090–2104.

Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D. (2013). Multidimensional networks: foundations of structural analysis. World Wide Web, vol. 16, no 5-6, p. 567–593.

Boley M., Horváth T., Poigné A., Wrobel S. (2010). Listing closed sets of strongly accessible set systems with applications to data mining. Theor. Comput. Sci., vol. 411, no 3, p. 691-700.

Fortunato S. (2010). Community detection in graphs. Physics Reports, vol. 486, no 3–5, p. 75- 174.

Galbrun E., Gionis A., Tatti N. (2014). Overlapping community detection in labeled graphs. Data Min. Knowl. Discov., vol. 28, no 5-6, p. 1586–1610.

Mougel P.-N., Rigotti C., Gandrillon O. (2012). Finding collections of k-clique percolated components in attributed graphs. In Pakdd(2), advances in knowledge discovery and datamining - 16th pacific-asia conference, pakdd 2012, kuala lumpur, malaysia, may 29 - june 1, 2012, vol. 7302, p. 181-192. Springer.

Negrevergne B., Termier A., Rousset M.-C., Méhaut J.-F. (2013). Paraminer: a generic pattern mining algorithm for multi-core architectures. Data Mining and Knowledge Discovery, vol. 28, no 3, p. 593-633.

Palla G., Derenyi I., Farkas I., Vicsek T. (2005, Jun). Uncovering the overlapping community structure of complex networks in nature and society. Nature, vol. 435, no 7043, p. 814–818.

Pasquier N., Taouil R., Bastide Y., Stumme G., Lakhal L. (2005). Generating a condensed representation for association rules. Journal Intelligent Information Systems (JIIS), vol. 24, no 1, p. 29-60.

Pernelle N., Rousset M.-C., Soldano H., Ventos V. (2002). Zoom: a nested Galois lattices-based system for conceptual clustering. J. of Experimental and Theoretical Artificial Intelligence, vol. 2/3, no 14, p. 157–187.

Seidman S. B. (1983). Network structure and minimum degree. Social Networks, vol. 5, p. 269–287.

Silva A., MeiraW., Jr., Zaki M. J. (2012, janvier). Mining attribute-structure correlated patterns in large attributed graphs. Proc. VLDB Endow., vol. 5, no 5, p. 466–477.

Soldano H. (2011, July). A modal view on abstract learning and reasoning. In M. Genesereth, P. Z. Revesz (Eds.), Ninth symposium on abstraction, reformulation, and approximation, sara 2011, cardona, catalonia, spain, p. 99–106. AAAI Press.

Soldano H. (2015a). Extensional confluences and local closure operators. In J. Baixeries, C. Sacarea, M. Ojeda-Aciego (Eds.), Formal concept analysis - 13th international conference, ICFCA 2015, nerja, spain, june 23-26, 2015, proceedings, vol. 9113, p. 128–144. Springer.

Soldano H. (2015b). Motifs fermés et abstraction : au delà des treillis. Revue d’Intelligence Artificielle, vol. 29, no 3-4, p. 321-348.

Soldano H., Santini G. (2014). Graph abstraction for closed pattern mining in attributed network. In T. Schaub, G. Friedrich, B. O’Sullivan (Eds.), European conference in artificial intelligence (ECAI), vol. 263, p. 849–854. IOS Press.

Soldano H., Santini G., Bouthinon D. (2015a, October 21-23). Abstract and local rulelearning in attributed networks. In F. Esposito, M.-S. Hacid, O. Pivert, Z. Ras (Eds.), Foundations of intelligent systems 22nd international symposium, ismis, vol. 9384, p. 313–323. Lyon, France, Springer.

Soldano H., Santini G., Bouthinon D. (2015b, November 9-11). Local knowledge discovery in attributed graphs. In A. Esposito (Ed.), 27th IEEE international conference on tools with artificial intelligence, ICTAI, vietri sul mare, italy, p. 250–257. IEEE Computer Society.

Soldano H., Ventos V. (2011). Abstract Concept Lattices. In P. Valtchev, R. Jäschke (Eds.), International conference on formal concept analysis (icfca), vol. 6628, p. 235–250. Springer, Heidelberg.

Szathmary L., Napoli A. (2005). Coron: A framework for levelwise itemset mining algorithms. In B. Ganter, R. Godin, E. M. Nguifo (Eds.), Third International Conference on Formal Concept Analysis (ICFCA’05), Lens, France, Supplementary Proceedings, p. 110–113.