ABSTRACT
The pattern or sub-graph detection in a graph has large areas of applications such as biology, Computer Vision, CAD, Electronics, Intelligence Analysis, and Social Networks. So the patterns or sub-graphs are detected either by comparing the ID of nodes or edge of the weight with the graph’s ID of the node or the edge’s weight. Sometimes the pattern detection is essential in an attributed graph—is a graph having n-nodes and m-attributes. In this scenario, how are the patterns or sub-graphs detected? The detection of pattern or sub-graphs in the attributed graph is carried out by comparing the attribute of the given pattern or sub-graph. Here the author proposes University Graph as Social Attributed Graph. The proposed University Graph consists of 20 nodes. Here a node is considered an employee. Each employee has a proper designation. Here the author considers four numbers of designations as the attribute of the node such as “Dean,” “Associate Dean,” “Professor,” and “Associate Professor,” respectively. So according to the definition of the attributed graph, the proposed University Attributed Graph has 20 nodes, and 4 attributes. From this University Attributed Graph, the author wants to detect the different form of patterns or sub-graphs such as “Line,” “Loop,” “Star,” and “Elongated Star” which comprise three, four, and five numbers of nodes, respectively. So the author proposes an algorithm which able to detect Line Pattern with 3 and 4 numbers of nodes, Loop Pattern with 3 and 4 numbers of nodes, Star Pattern with 4 numbers of nodes, and Elongated Star Pattern with 5 numbers of nodes respectively. The proposed algorithm has the following procedures: (i) NodePairGeneration, (ii) CreatePatterns3, (iii) DisplayPatterns3, (iv) CreatePatterns4, (v) DisplayPatterns4, (vi) CreatePatterns5, (vii) DisplayPatterns5, (viii) CreatePatterns6, and (ix) DisplayPatterns6, respectively. Procedure-(i) is for node-pair creation where the actual relation between the nodes. Procedure-(ii) and Procedure-(iii) for creation and display of line and loop pattern with 3 nodes. Procedure-(iv) and Procedure-(v) for creation and display of line and loop pattern with 4 nodes. The star pattern is created and displayed by Procedure-(vi) and Procedure-(vii). Finally, the elongated star pattern is created and displayed Procedure-(viii) and Procedure-(ix), respectively. The author has created two datasets namely (i) University Attributed Graph Dataset and (ii) Node-Attribute Dataset. The first dataset comprises the total numbers of nodes and the node-pairs where the node edge is formed in the University Attributed Graph. The second dataset comprises the Node-Attribute pairs which are the actual relationship between the node and its attribute. The algorithm has been implemented in C++ and Python programming and the result has been satisfactory.
