com.franz.agbase
Class SNAExtension

java.lang.Object
  extended by com.franz.agbase.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 generators 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)
          Bipartite 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)
          Bipartite 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)
          Bipartite depth first search.
 void registerGenerator(java.lang.String name, java.lang.Object[] parts)
          Register a generator 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 generators 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 generator in the AllegroGraph server. This generator 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 PrologSelectQuery.setQuery(String, 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 generator 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 generator 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 generator 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 generator 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 generator 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 generator 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 generator 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 generator 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 generator 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
Bipartite 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 generator defined previously with registerGenerator(String, Object[])
generator2 - a string that specifies a generator 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
Bipartite 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 generator defined previously with registerGenerator(String, Object[])
generator2 - a string that specifies a generator 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
Bipartite 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 generator defined previously with registerGenerator(String, Object[])
generator2 - a string that specifies a generator 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 generator 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 generator 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 generator 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 generator 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 generator 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 generator 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 generator 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 generator 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 generator 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 generator 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