Survey of Influential Nodes Identification in Online Social Networks

Common Terms And Concepts

Graph theory is used for studying topological analysis of the social networks. A social Network structure is the collection of individual users and the association or links between them. The structure can be represented as an undirected graph where the users can be represented as vertex and the links or relationships are edges (Figure 1). The relationships between two nodes can be of different types with different weights.

Figure 1.

Representation of an OSN as a Graph

Graph: A graph is a way of specifying relationships among a collection of items. A graph consists of a set of objects, called nodes or vertex, with certain pairs of these objects connected by links called edges (Figure 1).

• •

  Path: A path is simply a sequence of nodes with the property that each consecutive pair in the sequence is connected by an edge.

• •

  Connectivity: A graph is connected if for every pair of nodes, there is a path between them.

• •

  Diameter: It is calculated as the length of the longest shortest path between any pair of nodes in the graph.