 Home >
 Full text issues >
 Number 2 >
[Version française] 
Unilateral pretopological classification: an extension of the PretopoLIB library
Coralie Petermann, Vincent Levorato et Marc BuiAbstract
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, pretopoLIBTable of contents
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 unilateralconnectivity 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(∅) =∅

∀A⊂E,A⊂a(A)
We call interior defined on E any function i (.) of P (E) in P (E) such that:

i(E) =E

∀A⊂E, i(A)⊂A
Given a set E, a (.) and i (.), the couple s = (a (.), I (.)) is called a pretopolical structure E and the 3tuple (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).
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 realworld 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: apoconnected;

C: connected;
Strongly connected
Definition
∀A ⊆ E,A ̸ = ∅,F(A) = E (the only nonzero 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
∀A⊆E, A̸ =∅, F(A) =E. Else ∃B̸ =∅, B⊆E−F(A), such as A⊆F(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 nonempty open set equals E).
Apoconnected
Definition
∀ A, ∀ B two nonempty 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 EF(B), part of E which meets A.
Then:

E is SC⇒E is UC

E is UC⇒E is HC and E is AC

E is HC⇒E is C

E is AC⇒E is C
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 bottomup approach. We use a breadthfirst search looking for each node in order to agregate them together.
Algorithm
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 submodules, 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)

k_{avg} the mean degree of nodes ( k_{avg} = 5)

k_{max} the maximum degree of nodes ( k_{max} = 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)
Figure 7: pretopological space consisting of 50 nodes and oriented binary relations.
Figure 8: structuring with unilaterally connected components (7 components)
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 pConnected 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. 167256.
[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, ClermontFerrand, 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 129134, 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.