Intelligences Journal revue en intelligence économique
[Version française]

Unilateral pretopological classification: an extension of the PretopoLIB library

Coralie Petermann, Vincent Levorato et Marc Bui

Abstract

In this paper, we solve the issue of unilateral connectedness used in structuring components of directed graphs and networks. To achieve this, we define an algorithm to detect the components unilaterally related using pretopology, and we integrate this algorithm in the Java library PretopoLIB.

Keywords

classification, graph theory, pretopology, pretopoLIB

Full text

Introduction

Biological, social, technological, and information networks are often studied using graphs (Newman, 2003), and graph analysis is essential to understand the characteristics of these systems.

One of the most relevant features of graphs representing real systems is community structure. This problem is not yet solved despite the large number of proposed algorithms (Lancichinetti & Fortunato, 2009).

In this context, we introduced an algorithm called LP11 in order to classify oriented networks. This algorithm used the strongly connected components of maximum diameter p and obtained very satisfactory results (Levorato & Peterman 2011). In this article, we present the continuation of this work, because we are now focusing on other types of connectivities. We especially focus on the unilateral-connectivity used in pretopology. Indeed, we propose to store and use any information of complex networks, representing them as a pretopological space using oriented pretopological relations.

In this article, we present our algorithm detecting unilaterally related components, and the extension of PretopoLib library integrating it. In the first part we present the pretopology which is the mathematical theory used in our work. Then, we discuss the concepts of χ-connectivity which include unilateral connectivity. Then we present our detection algorithm using unilaterally related components. Finally, we conclude with the presentation of the PretopoLIB and some demonstrations.

Pretopology

The pretopology is a mathematical theory with axioms weaker than classical topology. Pretopology allows to express structural transformations of sets with interacting components such as the formation of coalitions among a population, alliance phenomena, processes of tolerance, acceptance and the emergence of collective behavior (Belmandt, 2011), (Levorato &Ahat, 2008).

We call closure defined on E, any function a (.) of P (E) in P (E) such that:

  • a() =

  • AE,Aa(A)

Agrandir Image1

Figure 1: closure a(A)

We call interior defined on E any function i (.) of P (E) in P (E) such that:

  • i(E) =E

  • AE, i(A)A

Image2

Figure 2: interior i(B)

Given a set E, a (.) and i (.), the couple s = (a (.), I (.)) is called a pretopolical structure E and the 3-tuple (S, a (. ) i (.)) is called a pretopologic space. Pretopology in a complex network is seen as a pretopological family on a given set E (Levorato, 2011).

Agrandir Image3

Figure 3: a pretopological family with 3 sets

Then, we can use different pretopological spaces on the same set to better model a phenomena. By this way, an accurate setting can be done easily and efficiently, and changing the value of one criteria is instantaneous.

χ-connectivities

Connectivity is an interesting concept for modeling problems related to the homogeneity or the structure of elements. However, the axioms of classical topology are often in conflicts with the real-world representation, particularly in the domain of social sciences (Belmandt, 2011).

Pretopology defines several types of connectivities. In this section, we consider a set E, defined by the pretopological structure s = (i(.),a(.)) of V type. We note σ = (O(.),F(.)) the operations of opening and closure on E. There are different types of connectivities, known as the χ-connectivities with χ corresponding to:

  • SC: strongly connected;

  • UC: unilaterally connected;

  • HC: hyperconnected;

  • AC: apo-connected;

  • C: connected;

Strongly connected

Definition

A E,A ̸ = ,F(A) = E (the only non-zero closed space is E)

E is SC iff A P(E),B P(E), there is a path from A to B.

Unilaterally connected

Definition

E is unilaterally connected (UC) iff: A E, A ̸ = , F (A) = E else B E, B ̸ = , B E − F (A) A F (B) ;

That is to say that E is UC if and only if for all A P(E) and for all B P(E) there is a path from A to B or from B to A.

Hyperconnected

Definition

AE, A̸ =, F(A) =E. Else B̸ =, BE−F(A), such as AF(B).

E is HC if and only if A P(E),B P(E), there is a path from A to B or there is a path from B to E -F (B), part of E which meets A (the closure of any non-empty open set equals E).

Apo-connected

Definition

A, B two non-empty subsets of E, we always have F (A) ∩ F (B) ̸ = .

E is AC if and only if A P(E),B P(E), M P(E) with a path from M to A and a path from M to B.

Connected

E is C if and only if A P(E),B P(E), there is a path from A to B or M P(E) with a path from M to B and a path from M to E-F(B), part of E which meets A.

Then:

  • E is SCE is UC

  • E is UCE is HC and E is AC

  • E is HCE is C

  • E is ACE is C

Image4

Figure 4: X-connectivities

In the next section, we describe precisely our algorithm detecting unilaterally connected components.

Our algorithm

Our method objective is to find unilaterally connected components using a bottom-up approach. We use a breadth-first search looking for each node in order to agregate them together.

Image5

Figure 5: BFS

Algorithm

Agrandir Image6

PretopoLIB

PretopoLib is a JAVA library that implements the concepts of pretopology (Levorato & Ben Amor, 2010). Its interest lies in the representation of data structures allowing data manipulation with set operations. Even if libraries implementing graph theory already exist, pretopoLIB is the only library that implements pretopological concepts. It provides a framework for developing efficient algorithms for data mining, structuring and modeling complex systems.

PretopoLib is written in JAVA by Marc Bui and Vincent Levorato (Levorato & Bui, 2008). The objective was to provide a reusable and distributable tool. It contains two main sub-modules, PretopoNotion that implements mathematical concepts and PretopoVisual which is used as a wrapper for data visualization.

In the next section, we present some illustrations of our proposed extension to the PretopoLIB.

Demonstrations

The PretopoLib visualization module is based on two external frameworks: Prefuse and JUNG, originally developped to represent graphs. Each framework can represent different areas according to our needs.

To test and analyze our method, we used a graph generator that allows complex generations of undirected or oriented realistics graphs. These generated data can easily be used as pretopological structures with oriented binary relations. We chose the LFR benchmark generator that Lancichinetti and Radicchi proposed in 2008 (Lancichinetti, Fortunato & Radicchi, 2008) with the following configuration:

  • n the number of nodes in the graph (n=50)

  • kavg the mean degree of nodes ( kavg = 5)

  • kmax the maximum degree of nodes ( kmax = 10)

  • minc, maxc the minimum and maximum size of communities ( minc = 2, maxc = 5)

  • μ, the mixing parameter ie for each node, the ratio between the number of outgoing edges and the number of incoming edges in the community (μ = 0.1)

Agrandir Image7

Figure 6: Example of mixed pretopological space (left) and visualization (right).

Image8

Figure 7: pretopological space consisting of 50 nodes and oriented binary relations.

Image9

Figure 8: structuring with unilaterally connected components (7 components)

Image10

Figure 9: structuring with strongly connected components (13 components)

As shown in the previous figures, we obtain different structures using unilaterally connected components or strongly connected components. Our algorithm allows different structures on the same pretopological space.

Conclusion

In this article, we focused on the dectection of unilaterally connected components. Our main contribution relies on the extension of the Java library PretopoLIB through the addition of an algorithm to detect these components.

We still work to optimize our algorithm, in order to decrease the complexity. The accuracy of results obtained is interesting in the context of large networks strongly connected. It would be interesting to speed up processing times to perform a serie of tests on networks with a high average degree and a high number of nodes.

Eventually, we would continue our work concerning network structuring using communities and extend our previous classification algorithm to UC structuration (Levorato & Petermann, 2011).

Bibliography

[1] Berge, C. (1970). Graphes et Hypergraphes. Dunod, Paris.

[2] Vincent Levorato, Coralie Petermann. Detection of Communities in Directed Networks based on Strongly p-Connected Components 3rd IEEE International Conference on Computational Aspects of Social Networks (CASoN’2011), Salamanca, Spain; 2011.

[3] A. Lancichinetti and S. Fortunato, Community detection algorithms: A comparative analysis, Phys. Rev. E, vol. 80, p. 056117, 2009.

[4] A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark graphs for testing community de- tection algorithms, Phys. Rev. E, vol. 78, no. 4, p. 046110, 2008.

[5] V.Levorato, S. Ben Amor, PretopoLib: la librairie JAVA de la Prétopologie, Extraction et Gestion des Connaissances (EGC), 2010.

[6] M. E. J. Newman. The Structure and Function of Complex Networks. SIAM Review, vol. 45, No. 2. (2003), pp. 167-256.

[7] ZT. Belmandt. Basics of pretopology. Hermann, 155 pages, ISBN: 978 27056 8077, 2011.

[8] Vincent Levorato and Murat Ahat. Modélisation de la dynamique des réseaux complexes as- sociée à la prétopologie. 9eme congrès de la Société Franc ̧aise de Recherche Opérationnelle et d’Aide à la Décision, ROADEF08, Clermont-Ferrand, France, February 2008.

[9] V. Levorato. Modeling Groups in Social Networks, In Proceedings of the 25th European Conference on Modelling and Simulation (ECMS’2011), pages 129-134, Krakow, Poland, 2011.

[10] V. Levorato. Contributions à la Modélisation des Réseaux Complexes: Prétopologie et Applications. PhD thesis, Université de Paris 8, 2008.

[11] V. Levorato, M. Bui (2008). Pretopolib. Dépôt de logiciel à l’Agence pour la Protection des Programmes. IDDN.FR.001.470004.000.R.P.2008.000.20600.

To cite this document :

Coralie Petermann, Vincent Levorato et Marc Bui, «Unilateral pretopological classification: an extension of the PretopoLIB library», Intelligences Journal [En ligne], Full text issues , Number 2 , URL : http://lodel.irevues.inist.fr/isj/index.php?id=213

Authors

Coralie Petermann
Prism, Université de Versailles St-Quentin-en-Yvelines, FR-78035 Versailles
Vincent Levorato
CESI, 959 rue de la Bergeresse, F-45160 Olivet
Marc Bui
LaISC, 41 rue Gay-Lussac, F-75005 Paris