Java implementation of TemporalRI algorithm for subgraph matching in temporal networks. The goal is to find all the occurrences of a query temporal graph Q in a target temporal graph T, such that timestamps of T's edges follow the same order induced by the timestamps of Q's edges and the difference between the maximum and the minimum timestamp of edges of each target occurrence is at most Delta.

References:

• Locicero G, Micale G, Pulvirenti A, Ferro A (2021). TemporalRI: A Subgraph Isomorphism Algorithm for Temporal Networks. International Conference on Complex Networks and Their Applications, (Complex Networks 2020), pp. 675-687.
• Micale G, Locicero G, Pulvirenti A, Ferro A (2021). TemporalRI: subgraph isomorphism in temporal networks with multiple contacts. Applied Network Science 6, 55 (2021), doi:10.1007/s41109-021-00397-0.
  
  

Requirements:

Java, version 14.0.1 or higher (https://www.oracle.com/it/java/technologies/javase-downloads.html)

Usage:

java -jar TemporalRI.jar -t targetFile -q queryFile [-d deltaThresh -u -o dumpOccFile]

Required parameters:

-t     Target network file
-q     Query network file

Optional parameters:

-d      Delta threshold for time window of events (by default delta is infinite)
-u      Treat target and query as undirected (by default networks are directed)
-o      Save query occurrences to specified output file (by default do not save, just count)

Examples of usage:

1. Find all occurrences of the query in the target with Delta equals to 10

java -jar TemporalRI.jar -t target.txt -q query.txt -d 10

2. Find all occurrences of the query in the target with infinite Delta. Treat the networks as undirected and save query occurrences found to file

java -jar TemporalRI.jar -t target.txt -q query.txt -u -o listOccurrences.txt

Input files format:

Target network is specified as a text file. The first row contains the number n of nodes in the network. The following n rows contain the id of a node followed by its label. Both strings and numbers can be specified as labels. Fields are separated by tab character (\t). The remaining rows contain the list of edges.

Each edge is specified by the id of the source node, followed by the id of the destination node, the timestamp of the edge and the edge label, according to the following format:

idSource    idDest    timestamp:label

'idSource', 'idDest' and 'timestamp:label' fields are separated by tab characters (\t). Both strings and numbers can be specified as labels. Multiple edges between two nodes but with different timestamps can be specified.

Example:

4
1	1
2	1
3	2
4	2
1	3	1245:5
1	4	1244:5
2	3	1245:5
1	3	1248:4
2	4	1246:4

Query network file has the same format, but node ids range from 0 to n-1, where n is the number of nodes.

Example:

3
0	1
1	1
2	1
0	1	1:1
0	2	2:1
0	1	2:2

Output file format:

By default the count of occurrences of the query in the target is returned. If an output file is specified, also the occurrences are returned and collected in the output file.

Each row contains an occurrence specified according to the following format:

(idNode1:lab1),(idNode2:lab2),...,(idNodeN:labN)    (idSource1,idDest1,timestamp1:lab1),(idSource2,idDest2,timestamp2:lab2),...,(idSourceM,idDestM,timestampM:labM)

where N and M are the number of nodes and edges of the occurrence, respectively.

Benchmark dataset:

Temporal networks: a dataset composed by 7 real temporal networks of different sizes.

Temporal queries: a dataset of queries with 3, 6, and 9 edges randomly extracted from the above 7 real temporal networks.

More details about the networks and how the queries were extracted are reported in:

• Micale G, Locicero G, Pulvirenti A, Ferro A (2021). TemporalRI: subgraph isomorphism in temporal networks with multiple contacts. Submitted to Applied Network Science (2021).