Valued graphs: Have one more factor of values attached to each line
Graph with Multiple Relations
Types
Subgraph: If set of nodes & lines is subset of G
Node-generated subgraph: Take a subset of nodes and consider all lines that are between the nodes in the subset
Used in the analysis of cohesive subgroups in networks
Line-generated subgraph: Take a set of subset of lines and consider all nodes that are incident with the lines in the subset
Maximal or not with respect to some property
Nodal Degree
Degree of a node: Number of lines that are incident with it
Ranges from 0 to (g-1)
Isolate: A node with degree equal to 0
Mean nodal degree = 2L/g
d-regular graph: Degrees of all of the nodes are equal
Measure of uniformity
Zero Variance
Variance of the degrees
Order: Number of vertices contained in the graph
Size/Length: Number of edges contained in the graph
Eccentricity of the vertex: Maximum distance between a vertex to all other vertices
Radius: Minimum eccentricity of any vertex in the graph
Diameter: Maximum eccentricity of any vertex in the graph
Density (Δ): Proportion of possible lines that are actually present in the graph
Maximum possible number of lines (m) = g(g-1)/2
Density (Δ) = Number of lines present (L)/Maximum Possible (m)
Ranges from 0 (no lines present) to 1 (all lines are present)
Complete graph: Density equal to 1 and all nodal degrees are equal to (g–1)
Empty graph: L = 0
Density of a subgraph
Walks
A sequence of nodes and lines, starting and ending with nodes, in which each node is incident with the lines following and preceding it in the sequence
Length of a Walk: Number of occurrences of lines in it
Origin: Starting node
Terminus: Ending node
Closed walk: A walk that begins and ends at the same node
Cycle & Semicycle
Tour: A closed walk in which each line in the graph is used at least once
Trails
A walk in which all of the lines are distinct, though some nodes may be included more than once
Circuit: A closed Trail
Eulerian trails: Special closed trails that include every line exactly once
Hamiltonian cycle: Every node in the graph is included exactly once
Paths
A walk in which all nodes and all lines are distinct
Connected Graphs: If there is a path between every pair of nodes in the graph
Components
Geodesics: A shortest path between two nodes
Eccentricity (Association) number of a node: Largest geodesic distance between that node and any other node
Ranges from 1 to (g-1)
Diameter: Length of the largest geodesic between any pair of nodes for a connected graph
Signed graph: Consists of Nodes, Lines, Valences attached to the lines
Complete signed graph
Signed Directed Graph
Connectivity of Graphs
Cutpoints
Cutset
Bridges
Measures
Node-Connectivity
Line-Connectivity
Isomorphic Graphs
Special Graphs
Complement
Tree
Bipartite
Valued Graph: Consists of Nodes, Lines, Values attached to the lines
Integer weighted digraph
Application
Markov chain
Multigraph
Hypergraph
Affiliation network: A two-mode network consisting of a set of actors and a set of events
Relation
Properties
Reflexive
Irreflexive
Not Reflexive
Symmetric
Antisymmetric
Non-Symmetric/Not Symmetric/Asymmetric
Transitive
Matrices
Adjacency Matrix/Sociomatrix
Incidence matrix
Hypergraphs are represented through incidence matrix
