com.franz.ag
Class SNAExtension

java.lang.Object
  com.franz.ag.SNAExtension

public class SNAExtension

extends java.lang.Object

This class implements Social Network Analysis tools.

An AllegroGraph triple store can be used to store a social network, The methods in this class implement search operations on this social network.

This class is instantiated from an AllegroGraph instance with a call to AllegroGraph.getSNAExtension().

Method Summary

UPI[][]	allBidirectionalSearchPaths(java.lang.Object start, java.lang.Object end, java.lang.String generator, int depth) Find all paths using bidirectional search.
UPI[][]	allBreadthFirstSearchPaths(java.lang.Object start, java.lang.Object end, java.lang.String generator, int depth) Search the triple store in breadth first fashion starting at start and looking for end, using generator to expand the search space.
UPI[][]	allDepthFirstSearchPaths(java.lang.Object start, java.lang.Object end, java.lang.String generator, int depth) Search the triple store in depth first fashion starting at start and looking for end, using generator to expand the search space.
UPI[]	bidirectionalSearch(java.lang.Object start, java.lang.Object end, java.lang.String generator, int depth) Find one path using bidirectional search.
UPI[]	breadthFirstSearch(java.lang.Object start, java.lang.Object end, java.lang.String generator, int depth) Search the triple store in breadth first fashion starting at start and looking for end, using generator to expand the search space.
void	copyGeneratorsFrom(SNAExtension from) Copy the generatores defined in another SNAExtension instance.
UPI[]	depthFirstSearch(java.lang.Object start, java.lang.Object end, java.lang.String generator, int depth) Search the triple store in depth first fashion starting at start and looking for end, using generator to expand the search space.
double	getBetweennessCentrality(java.lang.Object actor, java.lang.Object group, java.lang.String generator) Determine the betweenness centrality of an actor or group.
UPI[][]	getCliques(java.lang.Object node, java.lang.String generator, int minSize) Find all the cliques of which node is a member
double	getClosenessCentrality(java.lang.Object actor, java.lang.Object group, java.lang.String generator) Determine the closeness centrality of an actor or group.
double	getDegreeCentrality(java.lang.Object actor, java.lang.Object group, java.lang.String generator) Determine the centrality of an actor or group.
double	getDensity(java.lang.Object subgraph, java.lang.String generator) Determine the density of a subgraph.
UPI[]	getEgoGroup(java.lang.Object node, java.lang.String generator, int depth) Find the ego group of a node.
long	getNodalDegree(java.lang.Object node, java.lang.String generator) Find the number of nodes connected to a given node.
UPI[]	getNodalNeighbors(java.lang.Object node, java.lang.String generator) Find the nodes connected to a given node.
boolean	isClique(java.lang.Object subgraph, java.lang.String generator) Determine if a subgraph represents a clique.
void	mapBidirectionalSearch(java.lang.Object start, java.lang.Object end, java.lang.String generator, java.lang.String fn, int depth) Search for paths using bidirectional search and apply a server function to each.
void	mapBidirectionalSearchPathsBipartite(java.lang.Object start, java.lang.Object end, java.lang.String generator1, java.lang.String generator2, java.lang.String fn, int depth) Bipartitie bidirectional first search.
void	mapBreadthFirstSearch(java.lang.Object start, java.lang.Object end, java.lang.String generator, java.lang.String fn, int depth) Search the triple store in breadth first fashion starting at start and looking for end, using generator to expand the search space, and apply a server function to each path that is found.
void	mapBreadthFirstSearchPathsBipartite(java.lang.Object start, java.lang.Object end, java.lang.String generator1, java.lang.String generator2, java.lang.String fn, int depth) Bipartitie breadth first search.
void	mapCliques(java.lang.Object node, java.lang.String generator, java.lang.String fn, int minSize) Apply a server function to each clique found.
void	mapDepthFirstSearch(java.lang.Object start, java.lang.Object end, java.lang.String generator, java.lang.String fn, int depth) Search the triple store in depth first fashion starting at start and looking for end, using generator to expand the search space, and apply a server function to each path that is found.
void	mapDepthFirstSearchPathsBipartite(java.lang.Object start, java.lang.Object end, java.lang.String generator1, java.lang.String generator2, java.lang.String fn, int depth) Bipartitie depth first search.
void	registerGenerator(java.lang.String name, java.lang.Object[] parts) Register a generatore in the AllegroGraph server.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

copyGeneratorsFrom

public void copyGeneratorsFrom(SNAExtension from)
                        throws AllegroGraphException

Copy the generatores defined in another SNAExtension instance.

Parameters:

from - the SNAExtension from which the generators are copied

Throws:

AllegroGraphException

registerGenerator

public void registerGenerator(java.lang.String name,
                              java.lang.Object[] parts)
                       throws AllegroGraphException

Register a generatore in the AllegroGraph server. This generatore can be used in subsequent calls to search methods.

Parameters:

name - the name of the generator. If the name matches a previously defined generator in this instance, the older definition is overwritten.

parts - an Object array that defines the generator.

• If this argument is null, the named generator is deleted.
• If the argument is an array of length zero, nothing is done.
• If the first element of the array is a string, the entire array is the definition of a single clause.
• otherwise, each element of the array must be a Object array that defines a clause of the generator.

A generator clause specifies a set of neighbors that can be reached from a given node. The result of the generator is the union of the nodes from all the clauses.

• The first element of a clause is a string that identifies the nature of the clause and determines the format of the remaining elements.
• If the first element is the string "objects-of", "subjects-of", or "undirected", then the remaining elements of the clause are part references that may be strings in ntriples format, Value instances, or UPI instances.
  • "objects-of" -- this clause collects all the nodes that are objects of triples with the specified predicates.
  • "subjects-of" -- this clause collects all the nodes that are subjects of triples with the specified predicates.
  • "undirected" -- this clause collects all the nodes that are subjects or objects of triples with the specified predicates.
  This statement defines a generator with as single clause:

         registerGenerator("involved-with",
              new Object[]{ "objects-of", "!ex:kisses", "!ex:intimateWith" });
         

• If the first element is the string "select", the second element is a string containing a prolog query as in AllegroGraph.select(String). The query must specify a single result variable; this variable defines the result set of the generator clause. The pseudo-variable "node" denotes the origin node of the search.

          registerGenerator("in-movie-with",
              new Object[]{ "select", "(?x) (q ?x !franz:stars node)" });
          

  Additional elements in the clause specify a prolog variable and a value. To specify a predicate obtained from the application:

          registerGenerator("in-movie-with",
              new Object[]{ "select", "(?x) (q ?x ?pred node)", "?pred", v });
          

Throws:

AllegroGraphException

breadthFirstSearch

public UPI[] breadthFirstSearch(java.lang.Object start,
                                java.lang.Object end,
                                java.lang.String generator,
                                int depth)
                         throws AllegroGraphException

Search the triple store in breadth first fashion starting at start and looking for end, using generator to expand the search space.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search. In large graphs, this can be very expensive.

Returns:

an array of UPI instances containing the nodes on the first path found. If no path was found, this is an array of length zero. If a path is found, the start and end nodes will always be included.

Throws:

AllegroGraphException

mapBreadthFirstSearch

public void mapBreadthFirstSearch(java.lang.Object start,
                                  java.lang.Object end,
                                  java.lang.String generator,
                                  java.lang.String fn,
                                  int depth)
                           throws AllegroGraphException

Search the triple store in breadth first fashion starting at start and looking for end, using generator to expand the search space, and apply a server function to each path that is found.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

fn - a string that specifies a function in the server.

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search. In large graphs, this can be very expensive.

Throws:

AllegroGraphException

allBreadthFirstSearchPaths

public UPI[][] allBreadthFirstSearchPaths(java.lang.Object start,
                                          java.lang.Object end,
                                          java.lang.String generator,
                                          int depth)
                                   throws AllegroGraphException

Search the triple store in breadth first fashion starting at start and looking for end, using generator to expand the search space.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search. In large graphs, this can be very expensive.

Returns:

an array of paths. Each element is an array of UPI instances representing the nodes in one path. If no paths were found, this is an array of length zero.

Throws:

AllegroGraphException

depthFirstSearch

public UPI[] depthFirstSearch(java.lang.Object start,
                              java.lang.Object end,
                              java.lang.String generator,
                              int depth)
                       throws AllegroGraphException

Search the triple store in depth first fashion starting at start and looking for end, using generator to expand the search space.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search. In large graphs, this can be very expensive.

Returns:

an array of UPI instances containing the nodes on the first path found. If no path was found, this is an array of length zero. If a path is found, the start and end nodes will always be included.

Throws:

AllegroGraphException

mapDepthFirstSearch

public void mapDepthFirstSearch(java.lang.Object start,
                                java.lang.Object end,
                                java.lang.String generator,
                                java.lang.String fn,
                                int depth)
                         throws AllegroGraphException

Search the triple store in depth first fashion starting at start and looking for end, using generator to expand the search space, and apply a server function to each path that is found.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

fn - a string that specifies a function in the server.

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search. In large graphs, this can be very expensive.

Throws:

AllegroGraphException

allDepthFirstSearchPaths

public UPI[][] allDepthFirstSearchPaths(java.lang.Object start,
                                        java.lang.Object end,
                                        java.lang.String generator,
                                        int depth)
                                 throws AllegroGraphException

Search the triple store in depth first fashion starting at start and looking for end, using generator to expand the search space.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search. In large graphs, this can be very expensive.

Returns:

an array of paths. Each element is an array of UPI instances representing the nodes in one path. If no paths were found, this is an array of length zero.

Throws:

AllegroGraphException

bidirectionalSearch

public UPI[] bidirectionalSearch(java.lang.Object start,
                                 java.lang.Object end,
                                 java.lang.String generator,
                                 int depth)
                          throws AllegroGraphException

Find one path using bidirectional search.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search. In large graphs, this can be very expensive.

Returns:

an array of UPI instances containing the nodes on the first path found. If no path was found, this is an array of length zero. If a path is found, the start and end nodes will always be included.

Throws:

AllegroGraphException

mapBidirectionalSearch

public void mapBidirectionalSearch(java.lang.Object start,
                                   java.lang.Object end,
                                   java.lang.String generator,
                                   java.lang.String fn,
                                   int depth)
                            throws AllegroGraphException

Search for paths using bidirectional search and apply a server function to each.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

fn - a string that names a suitable server function.

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search. In large graphs, this can be very expensive.

Throws:

AllegroGraphException

allBidirectionalSearchPaths

public UPI[][] allBidirectionalSearchPaths(java.lang.Object start,
                                           java.lang.Object end,
                                           java.lang.String generator,
                                           int depth)
                                    throws AllegroGraphException

Find all paths using bidirectional search.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search. In large graphs, this can be very expensive.

Returns:

an array of paths. Each element is an array of UPI instances representing the nodes in one path. If no paths were found, this is an array of length zero.

Throws:

AllegroGraphException

mapBreadthFirstSearchPathsBipartite

public void mapBreadthFirstSearchPathsBipartite(java.lang.Object start,
                                                java.lang.Object end,
                                                java.lang.String generator1,
                                                java.lang.String generator2,
                                                java.lang.String fn,
                                                int depth)
                                         throws AllegroGraphException

Bipartitie breadth first search.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator1 - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

generator2 - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

fn - a string that names a suitable server function.

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search.

Throws:

AllegroGraphException

mapDepthFirstSearchPathsBipartite

public void mapDepthFirstSearchPathsBipartite(java.lang.Object start,
                                              java.lang.Object end,
                                              java.lang.String generator1,
                                              java.lang.String generator2,
                                              java.lang.String fn,
                                              int depth)
                                       throws AllegroGraphException

Bipartitie depth first search.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator1 - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

generator2 - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

fn - a string that names a suitable server function.

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search.

Throws:

AllegroGraphException

mapBidirectionalSearchPathsBipartite

public void mapBidirectionalSearchPathsBipartite(java.lang.Object start,
                                                 java.lang.Object end,
                                                 java.lang.String generator1,
                                                 java.lang.String generator2,
                                                 java.lang.String fn,
                                                 int depth)
                                          throws AllegroGraphException

Bipartitie bidirectional first search.

Parameters:

start - a string, Value instance or UPI instance that identifies the start node of the search.

end - a string, Value instance or UPI instance that identifies the end node of the search.

generator1 - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

generator2 - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

fn - a string that names a suitable server function.

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search.

Throws:

AllegroGraphException

getNodalNeighbors

public UPI[] getNodalNeighbors(java.lang.Object node,
                               java.lang.String generator)
                        throws AllegroGraphException

Find the nodes connected to a given node. The direction of the arcs is determined by the generator.

Parameters:

node - a string, Value instance or UPI instance that identifies a node in the graph.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

Returns:

an array of UPI instances

Throws:

AllegroGraphException

getNodalDegree

public long getNodalDegree(java.lang.Object node,
                           java.lang.String generator)
                    throws AllegroGraphException

Find the number of nodes connected to a given node. The direction of the arcs is determined by the generator.

Parameters:

node - a string, Value instance or UPI instance that identifies a node in the graph.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

Returns:

an integer

Throws:

AllegroGraphException

getEgoGroup

public UPI[] getEgoGroup(java.lang.Object node,
                         java.lang.String generator,
                         int depth)
                  throws AllegroGraphException

Find the ego group of a node. The ego group of a node is the set of other nodes in the graph (represented by the triple-store) that can be reached by following paths of at most length depth starting at node. The paths are determined using the generator to select neighbors of each node in the ego-group.

Parameters:

node - a string, Value instance or UPI instance that identifies a node in the graph.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

depth - an integer that limits the maximum depth of the search. A zero or negative value specifies an unrestricted search.

Returns:

an array of UPI instances representing the nodes in the ego group

Throws:

AllegroGraphException

getDensity

public double getDensity(java.lang.Object subgraph,
                         java.lang.String generator)
                  throws AllegroGraphException

Determine the density of a subgraph. This is the normalized average degree of the actors in the graph. Roughly, how many of the possible connections between actors are realized.

Parameters:

subgraph - a string, Value instance or UPI instance, or an array of these.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

Returns:

the numeric value

Throws:

AllegroGraphException

getDegreeCentrality

public double getDegreeCentrality(java.lang.Object actor,
                                  java.lang.Object group,
                                  java.lang.String generator)
                           throws AllegroGraphException

Determine the centrality of an actor or group. An actor centrality measure provides insight into how central or important an actor is in the group. Degree-centrality uses the number of actor connections (the degree) as a proxy for importance.

Parameters:

actor - If this argument is null, determine the group centrality. Otherwise, this argument is a string, Value instance or UPI instance that identifies a node in the graph.

group - a string, Value instance or UPI instance, or an array of these.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

Returns:

the numeric value

Throws:

AllegroGraphException

getClosenessCentrality

public double getClosenessCentrality(java.lang.Object actor,
                                     java.lang.Object group,
                                     java.lang.String generator)
                              throws AllegroGraphException

Determine the closeness centrality of an actor or group. An actor centrality measure provides insight into how central or important an actor is in the group. Closeness-centrality is the (normalized) inverse average path length of all the shortest paths between the actor and every other member of the group. (The inverse so that higher values indicate more central actors).

Parameters:

actor - If this argument is null, determine the group centrality. Otherwise, this argument is a string, Value instance or UPI instance that identifies a node in the graph.

group - a string, Value instance or UPI instance, or an array of these.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

Returns:

the numeric value

Throws:

AllegroGraphException

getBetweennessCentrality

public double getBetweennessCentrality(java.lang.Object actor,
                                       java.lang.Object group,
                                       java.lang.String generator)
                                throws AllegroGraphException

Determine the betweenness centrality of an actor or group. An actor centrality measure provides insight into how central or important an actor is in the group. Betweenness-centrality measures how much control an actor has over communication in the group.

The actor-betweenness-centrality of actor i is computed by counting the number of shortest paths between all pairs of actors (not including i) that pass through actor i. The assumption being that this is the chance that actor i can control the interaction between j and k.

Parameters:

actor - If this argument is null, determine the group centrality. Otherwise, this argument is a string, Value instance or UPI instance that identifies a node in the graph.

group - a string, Value instance or UPI instance, or an array of these.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

Returns:

the numeric value

Throws:

AllegroGraphException

isClique

public boolean isClique(java.lang.Object subgraph,
                        java.lang.String generator)
                 throws AllegroGraphException

Determine if a subgraph represents a clique.

Parameters:

subgraph - a string, Value instance or UPI instance, or an array of these.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

Returns:

true if every member of subgraph is linked to every other

Throws:

AllegroGraphException

getCliques

public UPI[][] getCliques(java.lang.Object node,
                          java.lang.String generator,
                          int minSize)
                   throws AllegroGraphException

Find all the cliques of which node is a member

Parameters:

node - a string, Value instance or UPI instance that identifies a node in the graph.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

minSize - an integer that specifies the minimum size of each clique. A zero or negative value specifies an unlimited size.

Returns:

an array of cliques. Each element is an array of UPI instances representing the nodes in one clique. If no cliques were found, this is an array of length zero.

Throws:

AllegroGraphException

mapCliques

public void mapCliques(java.lang.Object node,
                       java.lang.String generator,
                       java.lang.String fn,
                       int minSize)
                throws AllegroGraphException

Apply a server function to each clique found.

Parameters:

node - a string, Value instance or UPI instance that identifies a node in the graph.

generator - a string that specifies a generatore defined previously with registerGenerator(String, Object[])

fn - a string that names a suitable server function.

minSize - an integer that specifies the minimum size of each clique. A zero or negative value specifies an unlimited size.

Throws:

AllegroGraphException