graph-concepts-part1.txt

  /------------------------\
\|| Graph Concepts         ||/
/||  by Marko A. Rodriguez ||\
  \------------------------/

Graph Modeling
  Vertex, Edge (w/ properties)
  -- simple data model
  -- expressive data model


  a --knows--> b
  outE         inE
  outV         inV


    binary multi-relational graph:
        vertex ---edge---> vertex
    binary multi-relational attributed graph:
        vertex{properties} ---edges{properties}--> vertex{properties}   (aka. property graph)

    terminology  
        - a vertex has incident edges and adjacent vertices.
        - an edge has incident vertices and adjacent edges.
     * 1-hop = incident
     * 2-hop = adjacent


  ** easy in abstraction, but hard in implementation. **
        easy for the database user.
        hard for the database engineer.
   
Graph Encoding
    * the importance of colocation in computing.
        * database theory is about colocation in space and time.
            * space colocation is about ensuring what you access now will have multiple pieces of useful data (non discarded).
                - think buses
            * time colocation is about ensuring what you accessed in the past will be used in the future.   
                - think caches     

    * colocation has different requirements depending if on-disk, in-memory, en-route.
        - however, if you solve co-location variations of the same theme can be leveraged in other areas of the memory hiearchy.
        - adjacency list (vertex-centric) vs edge list (edge-centric)
            * adjacency list colocates edges with their incident vertices
                - access a vertex and you have cheap access to its edges (outE/inE).
                - to access the adjacent vertices of an edge requires another lookup.
            * edge list colocates vertices with their incide edges
                - access an edge an you have cheap access to its vertices (outV/inV).
                - to access the sibling edges of an incident vertex requires another lookup.
         
           *** adjacency lists denormalize edges and edge lists denormalize vertices.
         
               v[1]--knows-->[v[2],v[3],v[7],v[8],v[65],v[867]]     (adjacency list)
               
               
               e[1]: v[1]{properties}--knows-->v[2]{properties}     (edge list)
               e[2]: v[1]--knows-->v[3]
               ....
               v[1]--knows-->v[7]
               v[1]--knows-->v[8]
               ....              
               v[1]--knows-->v[65]
               v[1]--knows-->v[867]


            KEY    VALUE
            v[1]:{person}{a=b,c=d,e=f}{outE=[e[2],e[3],e[4]]}{inE=[....]}
            v[2]:{person}{....}{inE=[e[2]]}

            e[1]:{knows}{x=y,w=z}{outV=v[1]{person}{a=b,c=d,e=f}{outE=[v[2],v[3],v[4]]}{inE=[....]}}{inV=v[2]{person}{a=b,c=d,e=f}{outE=[v[2],v[3],v[4]]}{inE=[....]}}
            e[2]:{knows}{outV=v[1]{person}{a=b,c=d,e=f}{outE=[v[2],v[3],v[4]]}{inE=[....]}} inV=v{person}{a=b,c=d,e=f}{outE=[v[2],v[3],v[4]]}{inE=[....]}}

       - the majority of graph data is its edges |E| >> |V|.
            - edge lists are LARGE lists of SMALL amounts of data. (|E| >> |V|)
            - adjacency lists are SMALL lists of LARGE amounts of data. (|V| << |E|)                  
       
            
    * colocation has different requirements depending on end-user application.
        - for example, OLTP vs. OLAP
            - OLTP is about random access to small amounts of data. (optimiizing for time) 
            - OLAP is about linear access to large amounts of data. (optimizing for space)
        - when space is the constraint, you need disk (avoid memory)
            \_ OLAP: typically slowly computing over large regions of the graph (time is no problem -- disk)
        - when time is the constraint, you need memory (avoid disk)
            \_ OLTP: typically quickly computing over small regions of the graph (space is no problem -- memory)
       
  

Graph Algorithms
    - vertex lookup    : structural encoding    [explicit]
    - vertex similarity: structural relatedness
    - vertex centrality: structural influence
   

    Vertex Lookup:
        - classic database behaviors.
            - get a vertex by its id
            - get all vertices with a particular property
            - get the vertices adjacent to it.
        - a vertex has associated data.
            - properties (name, age)
            - edges (knows, likes, buys)
        - an edge has associated data
            - properties (weight, time)
            - vertices (to and from)
        ---------- 
        if you can get from any vertex to any other vertex via edges, then the graph is strongly connected.
            thus, the data associated with a vertex is the entirety of the graph.
        data access can be thought of as either being selection oriented or filter oriented.
                                                           |                    |
                                                            \ OLTP               \ OLAP



    Vertex Similiarty/Clustering:
        - two vertices are "the same" if they occupy the same topological region of the graph (i.e. v = u).
        - two vertices are similar if they occupy similar topological regions of the graph
               1.
                marko--buys-->horse
                marko--buys-->buggy
                  both horse and buggy are adjacent to marko, thus they are similar.    

              marko.out(bought).as(x).in(bought).where(not(marko)).out(bought).not(x)
             
               2.
                simon--buys-->rocket_car
                  marko and simon share no vertices in comon, they are dissimilar.
                    *** hypergraphically, they share the behavior of "buying" and thus are similar in a more abstract/hyper level.               
                lyndon--buys-->horse
                lyndon--buys-->buggy
                   both marko and lyndon are 2-step adjacent to each other, thus, they are similar.
   
        - the relationship between vectors and graphs


          Statistic 101:
            |- nominal data (discrete non-relational/euclidean categories)
            |- ordinal      (discrete euclidean rankings)
            |- scalar data (continuous euclidean metrics)  
            \
             \--- nominal: hair color, zipcode
             \\-- ordinal: country of origin, level of education
             \\\- scalar : weight, height, IQ

                 H    W  IQ
        marko: [5.11,150,165]
        simon: [5.7 ,145, 75]       
   

            |    m(*) 
            |  /     
            | /s(*)    
             -------

            * euclidean distance
            *  cosign similarity
            *  pearson correlation
            *  spearman correlation
            *  chi^2


        Rethink the graph in terms of matricies (tables)
          - a vertex is a vector in the matrix (a row in the table).
          - a property is a feature in the matrix (a column  in the table). 
            --- and edges?
                      -- think of the edges as explicit indices providing ways to generate implict properties.
                          . popularity: out('knows').count()
                          . consumerism: outE('bought').values('cost').mean()
          - the graph is then transformed into vectors then can be plotted in an n-dimensional space. (n the number of properties)
                - there are only so many metric
          - with transversals you don't have to explicitly create a matrix, but derive it 'on the fly'.
                - in essence, this is what graph clustering algorithms are doing where the features are the connectivity patterns.
                - graphs expose many matrices which are made salient through the traverals chosen.
          

            
     Vertex Centrality:
        - a vertex is central if its adjacent neighbors are central.  (recurrsively defined)
        - vertex centrality is computed through recurssion.
           1. every vertex is given 1/|V| energy.
           2. at every step, the vertex splits its current energy amongst its adjacent neighbors ((1/|V|)/|outE|)
           3. repeat until a steady state distribution is achieved.
                ^--- will be achieved as long as the graph is connected, and recurrent.
                                                                 |                |
                                                                  \ no islands     \ no sinks
           a steady state distribution means that the energy a vertex sends to its outgoing neighbors is exactly the same amount of energy is receives from its incoming neighbors.
           thus, the algorithm can be called "statically dynamic" -- energy is flowing, but the relative distribution of energy never changes.
           a vertex's relative distribution of energy defines the centrality of the vertex.
             -- since all vertices started with (1/|V|) energy points, the sum total of energy in the system is 1 as (1/|V| * |V| = 1).
             -- thus, the steady state distribution yields a probability distribution.
             -- the centrality of a vertex is understood as the probability of selecting that vertex from V.
                    - the more likely that vertex is picked, the higher its centrality/influence/locality/presense/etc.