# graph_analytics¶

The graph analytics toolkit contains methods for analyzing a SGraph. Each method takes an input graph and returns a model object, which contains the training time, an SFrame with the desired output for each vertex, and a new graph whose vertices contain the output as an attribute. Note that all of the methods in the graph analytics toolkit are available from the top level turicreate import.

For this example we download a dataset of James Bond characters to an SFrame, then build the SGraph.

>>> from turicreate import SFrame, SGraph
>>> url = 'https://static.turi.com/datasets/bond/bond_edges.csv'
>>> g = SGraph().add_edges(data, src_field='src', dst_field='dst')


The degree_counting.create() method computes the inbound, outbound, and total degree for each vertex.

>>> from turicreate import degree_counting
>>> deg = degree_counting.create(g)
>>> deg_graph = deg['graph'] # a new SGraph with degree data attached to each vertex
>>> in_degree = deg_graph.vertices[['__id', 'in_degree']]
>>> out_degree = deg_graph.vertices[['__id', 'out_degree']]


The connected_components.create() method finds all weakly connected components in the graph and returns a ConnectedComponentsModel. A connected component is a group of vertices such that there is a path between each vertex in the component and all other vertices in the group. If two vertices are in different connected components there is no path between them.

>>> from turicreate import connected_components
>>> cc = connected_components.create(g)
>>> print cc.summary()

>>> cc_ids = cc.get('component_id')  # an SFrame
>>> cc_ids = cc['component_id']      # equivalent to the above line
>>> cc_graph = cc['graph']


The shortest_path.create() method finds the shortest directed path distance from a single source vertex to all other vertices and returns a ShortestPathModel. The output model contains this information and a method to retrieve the actual path to a particular vertex.

>>> from turicreate import shortest_path
>>> sp = shortest_path.create(g, source_vid=123)
>>> sp_sframe = sp['distance']
>>> sp_graph = sp['graph']
>>> path = sp.get_path('98')


The triangle_counting.create() counts the number of triangles in the graph and for each vertex and returns a TriangleCountingModel. A graph triangle is a complete subgraph of three vertices. The number of triangles to which a vertex belongs is an indication of the connectivity of the graph around that vertex.

>>> from turicreate import triangle_counting
>>> tc = triangle_counting.create(g)
>>> tc_out = tc['triangle_count']


The pagerank.create() method computes the pagerank for each vertex and returns a PagerankModel. The pagerank value indicates the centrality of each node in the graph.

>>> from turicreate import pagerank
>>> pr = pagerank.create(g)
>>> pr_out = pr['pagerank']


The label_propagation.create() method computes the label probability for the vertices with unobserved labels by propagating information from the vertices with observed labels along the edges. The method returns a LabelPropagationModel, which contains the probability that a vertex belongs to each of the label classes.

>>> from turicreate import label_propagation
>>> import random
>>> def init_label(vid):
...     x = random.random()
...     if x > 0.9:
...         return 0
...     elif x < 0.1:
...         return 1
...     else:
...         return None
>>> g.vertices['labels'] = g.vertices['__id'].apply(init_label, int)
>>> m = label_propagation.create(g)
>>> labels = m['labels']


The K-core decomposition recursively removes vertices from the graph with degree less than k. The value of k where a vertex is removed is its core ID; the kcore.create() method returns a KcoreModel which contains the core ID for every vertex in the graph.

>>> from turicreate import kcore
>>> kc = kcore.create(g)
>>> kcore_id = kc['core_id']


Graph coloring assigns each vertex in the graph to a group in such a way that no two adjacent vertices share the same group. graph_coloring.create() method returns a GraphColoringModel which contains the color group ID for every vertex in the graph.

>>> from turicreate import graph_coloring
>>> color = graph_coloring.create(g)
>>> color_id = color['color_id']
>>> num_colors = color['num_colors']


For more information on the models in the graph analytics toolkit, plus extended examples, please see the model definitions and create methods in the API documentation, as well as the graph analytics chapter of the User Guide.

## connected components¶

 connected_components.create Compute the number of weakly connected components in the graph. connected_components.ConnectedComponentsModel A ConnectedComponentsModel object contains the component ID for each vertex and the total number of weakly connected components in the graph.

## degree counting¶

 degree_counting.create Compute the in degree, out degree and total degree of each vertex. degree_counting.DegreeCountingModel Model object containing the in degree, out degree and total degree for each vertex,

## graph coloring¶

 graph_coloring.create Compute the graph coloring. graph_coloring.GraphColoringModel A GraphColoringModel object contains color ID assignments for each vertex and the total number of colors used in coloring the entire graph.

## k-core¶

 kcore.create Compute the K-core decomposition of the graph. kcore.KcoreModel A KcoreModel object contains a core ID for each vertex, and the total number of cores in the graph.

## label propagation¶

 label_propagation.create Given a weighted graph with observed class labels of a subset of vertices, infer the label probability for the unobserved vertices using the “label propagation” algorithm. label_propagation.LabelPropagationModel A LabelPropagationModel computes the probability of each class label for each unlabeled vertex.

## pagerank¶

 pagerank.create Compute the PageRank for each vertex in the graph. pagerank.PagerankModel A PageRankModel object contains the pagerank value for each vertex.

## shortest path¶

 shortest_path.create Compute the single source shortest path distance from the source vertex to all vertices in the graph. shortest_path.ShortestPathModel Model object containing the distance for each vertex in the graph to a single source vertex, which is specified during turicreate.shortest_path.create().

## triangle counting¶

 triangle_counting.create Compute the number of triangles each vertex belongs to, ignoring edge directions. triangle_counting.TriangleCountingModel Model object containing the triangle count for each vertex, and the total number of triangles.