LineGraphCreator

Version 100520

Primary source is now
Evans, Tim; Lambiotte, Renaud (2014): LineGraphCreator. figshare. 10.6084/m9.figshare.1184430

This simple C++ code reads in a graph and creates its weighted line graph. These line graphs are defined in the paper by T.S.Evans and R.Lambiotte, Line Graphs, Link Partitions and Overlapping Communities, Phys.Rev.E 80 (2009) 016105 arXiv:0903.2181. Please cite this paper and acknowledge use of this code if you use this code.

A later paper Edge Partitions and Overlapping Communities in Complex Networks, European Physical Journal B, 77 (2010) 265–272 (arXiv:0912.4389) covers in more detail the case where one is interested in the different line graphs of a weighted graph.

This code been used successfully on an unweighted graph which produced 5.5e8 stubs in its line graph, though a special machine was used for this as it needs more than 4Gb of RAM memory. On a 4Gb machine a line graph with 4.5e7 stubs was created using this code.

This version should do all types of graph. It has been used extensively on input graphs G which are unweighted and undirected. It has only been lightly tested on weighted but undirected input graphs G. It has not been tested on directed graph input but since the weighted input graphs produce directed line graphs some relevant aspects have been tested. This is based on a java code that has had much more testing. There is an older version of the code available at a Weighted line graphs page.

Usage

linegraphcreator -i input_file -o output_file [options]

For example try

linegraphcreator -i input/BowTieinputEL.dat -o BowTieWLGoutputEL.dat -t 2

File Formats

Self-loops may be created but it is not clear if the code works for these.

Multiple edges between the same two vertices may also be created but again it is not clear if the code will work properly in this case.

The output files are in the same format. The vertices of the line graph are the edges of the original graph and are again numbered from 0 in the order of the edges given in the input file for the original graph G.

Example One

0 1
0 2
1 2
2 3
2 4
3 4

linegraphcreator -i input/BowTieinputEL.dat -o BowTieWLGoutputEL.dat -t 2

0	1	1
0	2	1
1	2	0.333333
1	3	0.333333
1	4	0.333333
2	3	0.333333
2	4	0.333333
3	4	0.333333
3	5	1
4	5	1

Example Two

0 1 1
0 2 2
1 2 1
2 3 1
2 4 1
3 4 1

linegraphcreator -i input/BowTieWinputEL.dat -o BowTieW_WLGoutputEL.dat -t 2 -w

0	1	1
1	0	1
0	2	1
2	0	1
1	2	0.333333
1	3	0.333333
1	4	0.333333
2	1	0.5
2	3	0.25
2	4	0.25
3	1	0.5
3	2	0.25
3	4	0.25
4	1	0.5
4	2	0.25
4	3	0.25
3	5	1
5	3	1
4	5	1
5	4	1

Basic Compiling

g++ -o linegraphcreator TseGraph.cpp main.cpp

If you want to get more complicated, try optimising options -O2

g++ -c -O2 -o TseGraph.o TseGraph.cpp
g++ -c -O2 -o main.o main.cpp
g++ -o linegraphcreator TseGraph.o main.o

makefile

CC=g++
CFLAGS=-c -Wall
LDFLAGS=-O2

all: linegraphcreator

linegraphcreator: main.o TseGraph.o
	$(CC) $(LDFLAGS) main.o TseGraph.o -o linegraphcreator

main.o: main.cpp
	$(CC) $(CFLAGS) main.cpp

factorial.o: factorial.cpp
	$(CC) $(CFLAGS) TseGraph.cpp

clean:
	rm -rf *o linegraphcreator

Using on the Imperial altix HPC machine

 module load intel-suite icpc -xP -mcmodel=large -i-dynamic -o linegraphcreator TseGraph.cpp main.cpp

qsub axlgc.sh

#!/bin/bash
#PBS -l walltime=24:00:00
#PBS -l mem=60Gb
#PBS -l ncpus=4
#PBS -m abe
# Script to run linegraphcreator (C++) on ALTIX
#
# compile using
#module load intel-suite
#icpc -mcmodel=large -i-dynamic -o linegraphcreator TseGraph.cpp main.cpp

module load intel-suite
export NAMEROOT=IC090729stempt
export NAMEEND=inputEL.dat
cp -v ${HOME}/linegraphcreator/input/${NAMEROOT}${NAMEEND} ${TMPDIR}
echo Running ${NAMEROOT}
${HOME}/linegraphcreator/linegraphcreator  -i ${TMPDIR}/${NAMEROOT}${NAMEEND} -o ${TMPDIR}/${NAMEROOT}WLGoutputEL.dat -t 2
cp -v ${TMPDIR}/${NAMEROOT}WLG* ${HOME}/linegraphcreator/output/