This repository contains several software projects developed during my PhD thesis at Telecom - Bretagne. Since the software and algorithms were mostly written for papers and thus in a rush, the code may not be the best and cleanest code you may ever seen.
However, in an effort to write clean code, I try to document all the code and to automate the building process. To do this I use CMake (I hope you know the basics of CMake).
- Notice and license
- Installing CMake
- Installing and configuring Tulip
- Installing and configuring ATLAS
- Projects
Copyright (c) 2014 Juan David Cruz Gómez and Telecom - Bretagne
juan.cruzgomez@telecom-bretagne.eu juandavidcruz@gmail.com
Licensed under the EUPL, Version 1.2 or – as soon theywill be approved by the European Commission - subsequent versions of the EUPL (the "Licence");
You may not use this work except in compliance with the Licence. You may obtain a copy of the Licence at:
https://joinup.ec.europa.eu/software/page/eupl5
Unless required by applicable law or agreed to inwriting, software distributed under the Licence isdistributed on an "AS IS" basis, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the Licence for the specific language governing permissions and limitations under the Licence.
Some of the sub-projects are linked against the Tulip library.
Specifically, the version of Tulip that has been used is the 3.8 and is the only one I have made tests on.
You can find the source of the 3.8 version of Tulip here.
Now, if you just don't want to compile and install, you can download the packages for your distribution. In Debian (I guess in Ubuntu also) you can install Tulip 3.7 using:
juancrug@juandavid-office:~$ sudo apt-get install tulip libtulip-dev
Note that you need to install the development package to compile the software in this suite.
ATLAS stands for Automatically Tuned Linear Algebra Software so, it's a linear algebra package that implements several vector/matrix operations ready to use.
Important note: save the installation prefix for ATLAS. I usually chose to install these kind of libraries in ~/
Follow the instructions here to configure ans install ATLAS.
Why do you need to configure and build ATLAS? well, this library is used by several algorithms and it depends on the system being used, e.g., 32 bits with 512 Kb L2 cache is different than 64 bits processors with 1024 Kb L2 cache and 8 cores.
Sorry, this is the way that it is.
This is the set of projects I have made these years at Telecom - Bretagne.
Basic algorithms and libraries I have created for my other algorithms. Since I do not like the disorder and I do not want to rewrite all over again the same code, I decided to write libraries and use them as tools whenever I needed.
That's a lot work for me I think, but it's a lot cleaner and centralized. Even more, I think that the excuse I'm a computer scientist, so I write messy code is just lame.
This library encapsulates the behavior of a matrix object and implements several operations like matrix-matrix multiplication and scalar multiplication.
As you can imagine, this library has to be linked against the ATLAS library.
Find the code here.
This library isolates the MDS-SMACOF algorithm from Borg & Groenen and makes it available for other algorithms such as the boundary communities visualization algorithm.
Find the code here.
This library implements a data structure called trie (pronounced as try) that is used by the Galois lattice generator algorithm. The importance of this structure lies in the access speed to stored elements: this is an indexed tree that allows to rapidly find nodes with certain data.
This is used for to index the concepts of the lattice while being generated.
This is the first version of the algorithm for detecting communities: first, the version in which the weights of the edges of the graphs are modified using the information from a SOM clustering, then the Louvain's algorithm is used to find the final communities.
Find the code here.
#####Papers
-
Analyse intégrée des réseaux sociaux pour la détection et la visualisation de communautés - TSI 2014
-
Semantic Clustering of Social Networks using Points of View - Coria 2011
-
Point of View Based Clustering of Socio-Semantic Network - EGC 2011
This algorithm uses the affiliation matrices obtained from two partitions, one from the structural variable and another from the attributes of the nodes of the network. By the multiplication of these matrices we obtain a contingency matrix, in which each position is in fact the number of agreements between the groups of both partitions, i.e., the number of nodes placed on the same group in both partitions.
Then, by manipulating (splitting) the rows of the contingency matrix it is possible to find new communities: the idea is to maximize the variance of the new potential groups.
Find the code here.
- Integrating heterogeneous information within a social network for detecting communities - ASONAM 2013
- Information integration for detecting communities in attributed graphs - CASoN 2013
This is the third version of the community detection algorithm. This algorithm builds a galois lattice to integrate the affilaition matrix generated from the structural variable and the features of the nodes represented as a binary matrix. These two matrices are concatenated into one, and from it the lattice is calculated.
Then the concepts from the lattices are integrated according to their depth in the lattice: the more deep actors are in the lattice, the more central they are for the community.
Find the code here.
- Not papers yet :-(
This community detection algorithm could be seen as the 1.5 version, however it has been written in Java and at this stage is not fully integrated into the platform.
This algorithm modifies the Louvain's algorithm to introduce an entropy criterion and change the way to communities are fused.
Find the code here.
This is the visualization algorithm that divides the nodes into two kinds: boundary or border nodes and inner nodes. The first kind are the nodes that connect different communities while the second are the nodes connected only with other nodes inside theirs own communities.
Find the code here.
- Analyse intégrée des réseaux sociaux pour la détection et la visualisation de communautés - TSI 2014
- Community detection and visualization in social networks: Integrating structural and semantic information - TIST 2013
- Layout Algorithm for Clustered Graphs to Analyze Community Interactions in Social Networks - ASONAM 2012
These are the Tulip plugin version of the algorithms, i.e., the plugin definitions for the algorithms in such a way they can be used from Tulip menu.
These plugins should be compiled from the root folder. Get to the code here and follow the instructions there to compile.
This folder is meant to contain importers from different king of files. Up to now there is only the DIMACS graph files importer.
This folder contains the Louvain's and the PoV community detection algorithms.
Plugin for the visualization algorithm
This plugin implements a way to test different points of view using the PoV community detection algorithm plus the layout method.