Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 164 https://internationalpubls.com Optimizing Graph Theory Algorithms for Social Network Analysis Susanta Kumar Sahoo1, Sasmita Mishra2 1Department of Computer Science Engineering & Applications, IGIT Sarang, Odisha, India susantasahoo79@gmail.com 2Department of Computer Science Engineering & Applications, IGIT Sarang, Odisha, India sasmita.mishra.csea@gmail.com Article History: Received: 16-04-2024 Revised: 10-06-2024 Accepted: 24-06-2024 Abstract Social network analysis (SNA) leverages graph theory to understand and visualize the complex relationships and structures within social networks. This research paper explores the optimization of graph theory algorithms tailored for SNA, focusing on efficiency improvements in handling large-scale networks. The study reviews key graph theory concepts, identifies common challenges in SNA, and evaluates various optimization techniques. Practical applications and case studies are presented to demonstrate the impact of these optimizations in real-world scenarios. Keywords: Graph Theory, Algorithms, SNA. 1. Introduction The dissemination of information and even political movements are all shaped by social networks, which influence everything from personal relationships to professional connections. Individuals or entities (nodes) and their interactions (edges) make up these networks, which include offline social structures as well as online social platforms like Facebook, Twitter, and LinkedIn. The investigation of these organizations, known as Informal community Examination (SNA), uses chart hypothesis to show and break down these complicated frameworks [1]. The mathematical foundation required to represent and investigate the intricate web of connections that makes up social networks is provided by graph theory. Researchers and practitioners can discover community structures, predict future trends, and gain insight into the dynamics of networks by utilizing graph theory. In any case, the sheer scale and intricacy of contemporary informal communities’ present huge difficulties to customary diagram hypothesis calculations. Optimizing graph theory algorithms is now a necessity as the amount of data from social networks grows at an exponential rate. Many modern social networks have millions of nodes and billions of edges, requiring a lot of memory and computation. The dynamic nature of social networks, where edges and nodes are constantly added or removed, makes it even more difficult to solve these problems [2]. Several real-time applications, such as recommendation systems, fraud detection, targeted marketing, and public health monitoring, require optimized graph theory algorithms. We can guarantee timely and accurate analysis, facilitate better decision-making, and encourage innovation in a variety of fields by increasing these algorithms' efficiency and scalability [3]. The goal of this paper is to : • Go over the fundamental ideas of graph theory that are relevant to SNA. • Identify obstacles that arise when analyzing massive social networks. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 165 https://internationalpubls.com • Assess streamlining procedures for diagram hypothesis calculations. • Provide examples of real-world uses for optimized algorithms in case studies. The theoretical and practical aspects of optimizing graph theory algorithms for SNA are covered in this paper [4]. We begin by looking at fundamental ideas in graph theory and how they apply to social networks. The unique difficulties that large-scale social network analysis presents, such as scalability, dynamic nature, and computational complexity [5], are then discussed. After that, we delve into a variety of optimization strategies, including enhancements to algorithms, cutting-edge data structures, and specialized hardware. The efficacy of these methods in improving the performance and scalability of graph algorithms is the basis for their evaluation [6]. Finally, we present case studies from a variety of application areas to show how optimized graph theory algorithms can be used in real-world situations. These case studies demonstrate the transformative power of optimization methods for dealing with current SNA issues [7]. This paper aims to contribute to ongoing efforts to optimize graph theory algorithms for social network analysis by providing a comprehensive overview of the current state of research and practical applications. Future research and development in this crucial field will benefit from the insights and findings presented here, allowing for advancements that can keep up with the ever-changing social network landscape. 2. Graph Theory Fundamentals The study of graphs, mathematical structures used to model pairwise relationships between objects, is known as graph theory. These objects are typically individuals or entities in the context of social network analysis (SNA), and the relations are the interactions or connections that exist between them [8]. The fundamental ideas of graph theory, such as the fundamental metrics and common representations that are necessary for comprehending and analyzing social networks, are discussed in this section. A graph G is made up of a set of edges E and a set of nodes V, which are also known as vertices in graph theory. A pair of nodes in V are connected by each edge e in E. G = (V, E) is the formal representation of a graph. -Nodes (Vertices): These represent the network's constituent parts. Nodes typically represent individuals in a social network. - Edges: Depict the relationships or connections that exist between nodes. Edges can represent friendships, communications, or other interactions in a social network. - Directed Graph: Edges in this graph have a direction, indicating a one-way relationship (such as a relationship between Twitter followers). - Undirected Graph: Edges in this graph do not have a direction, indicating a relationship (like Facebook friendships, for instance). Degree centrality is a proportion of the quantity of direct associations a hub has. The most influential or connected nodes in a network can be identified using this straightforward but effective metric [9]. - Level of a Hub v: The quantity of edges episode to v. - In-degree: The quantity of edges that enter a node (important for directed graphs). Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 166 https://internationalpubls.com - Out-degree: The number of node-to-edge outgoing edges (important for directed graphs). For a node v in formal terms: Degree Centrality(v) = deg(v) Centrality and Betweenness The degree to which a node is located on the shortest paths between other nodes is measured by betweenness centrality. It gives a number to how important a node is in terms of how it controls how information moves through the network. A general idea of how clustered the network is is provided by the average clustering coefficient of the graph. Effective portrayal of charts is basic for upgrading diagram calculations. Adjacency matrices and adjacency lists are the two most prevalent representations. Simple adjacency matrices can be space-inefficient for large, sparse graphs, though. A graph is represented by an array of lists in an adjacency list. A list of adjacent nodes to each node is included in each list, which corresponds to a node. For sparse graphs, this representation uses less space. For instance, suppose a graph has nodes V equal to 1, 2, 3, and edges E equal to (1, 2), (1, 3): - Node 1: [2, 3] - Node 2: [1] - Node 3: [1] The foundation for analyzing and optimizing social networks is an understanding of the fundamental concepts and graph representations [10]. Measurements like degree centrality, betweenness centrality, and grouping coefficient give experiences into the design and elements of organizations. Adjacency matrices and adjacency lists are effective graph representations that are necessary for the implementation and optimization of graph algorithms, particularly when dealing with large-scale social networks. We will discuss the specific difficulties of social network analysis and the optimization methods used to solve them in the following sections. Main results: Theorem 2.1. Let 1G and 2G be SNA graphs then ( )21 GGVD  is a sna-set in 21 GG  if and only if one of the following conditions holds. (i) For each ( ) ( ) DGVGVv v  21 , is a dominating in vG2 and ( ) ( )  GVu uGVD   2 . (ii) ( ) DGV 1 is a complementary tree dominating in 1G and ( ) DGV v 2 whenever ( ) DGVv  1 and ( ) DGV v 2 is dominating in vG2 whenever ( ) .1 DGVv − Proof. Suppose ( ) .1 = DGV Let ( )1GVv and ( ) .2 DGVx v − Hence ( ) .21 DGGVx −  Since D is a ctd-set of 21 GG  There exists Dy  such that ( ) .1, 21 =yxd GG  Since ( )vGVx 2 and ( ) 1, 21 =yxd GG  either ( )vGVy 2 or vy = .If vy = then ( ) ,1 DGVy  a contradiction. Therefore ( ) DGVy v  2 is a dominating set of vG2 Since ( ) ,1 = DGV ( ) ( )  1 2 GVu uGVD   . Hence (i) holds. Suppose ( )  DGV 1 and ( ) ( )11 GVDGV  . Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 167 https://internationalpubls.com Let ( ) DGVx − 1 it follows ( ) DGGVx − 21  . Let D is a dominating set of 21 GG  there exists Dy  such that ( ) .1, 21 =yxd GG  If ( )1GVy then ( ) DGVy  1 then ( ) .1, =yxdG Hence ( ) DGV 1 is a dominating set in .1G Now we have to prove ( ) DGV 1 is a complementary tree dominating set in 1G it is enough to prove ( ) − DGV 1 is a tree. Let ( ) ., 1 DGVyx − Since − DGGV )( 21  is a tree T. Therefore )(, 1GVyx  there exist ( )xGVu 2 and v ( )yGV 2 . Since T is SNA and acyclic. There exists a unique path between u and v .Hence x and y are the vertices transverse from u and v . Hence 𝑉(𝐺1) ∩ 𝐷is a ctd-set in G1. Suppose DGVv  )( 1 and ( ) − DGV v 2 . Let DGVu v − )( 2 . Since )()( 11 GVDGV  there exists .)( 1 DGVw − Since − DGGV )( 21  is a tree. There exists a unique path between u - w with vertices from .)( 21 DGGV − However any u-w path must contain a vertex v which is impossible. Hence .)( 2 =− DGV v Hence .)( 2 DGV v  Suppose DGVv − )( 1 . Let DGVx v − )( 2 . This implies that .)( 21 − DGGVx  Since D is a ctd-set in 21 GG  there exists Dy  such that ( ) .1, 21 =yxd GG  Consequently vy = or ).( 2 vGVy Since Dy and .)( 1 DGVv − Hence vy  then it follows )( 2 vGVy now ( ) 1, 21 =yxd GG  implies ( ) .1, 2 =yxd vG Hence DGV v )( 2 is a dominating set in vG 2 .Therefore (iii) holds. Conversely, Suppose (i) holds. Let .)( 21 DGGVx −  Suppose )( 1GVx .Since DGV x )( 2 is dominating set in xG2 and .)( 2  DGV x Let .)( 2 DGVu x  Then 1),( 21 =yxd GG  . Suppose )( 1GVx then there exist )( 1GVy such that ( ).2 yGVx since DGV y )( 2 is a dominating set in yG2 and DGVx y − )( 2 there exist DGVt y  )( 2 such that 1),( 21 =txd GG  then D is a dominating set in 21 GG  . Since ( ) ( ) ( ) .12 1 =  DGVandGVD GVu u Consequently, )()()( 1 )( 221 GVDGVDGGV GVv v −=−   .Let qpDGGVqp − ,)(, 21  .If DGVqp v − )(, 2 for some )( 1GVv then there is a path with vertices qvp ,, in .)( 21 DGGV − If )(, 1GVqp  .Then there is a tree which contains a p-q path in DGGV −)( 21  .Since G1 is SNA. If ( )1GVp and ( ) DGVq v − 2 for some ( )1GVv then DGGV −)( 21  contains a tree with vertices p and v . Suppose vp  since G1 is connected then DGGV −)( 21  contains a tree with vertices qvp ,, .Suppose ( ) DGVp v − 2 and ( )wGVq 2 for some ).(, 1GVwv  Since G1 is connected Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 168 https://internationalpubls.com then there exist a tree with vertices qwvp ,,, in DGGV −)( 21  .Hence DGGV −)( 21  is SNA and acyclic. Therefore DGGV −)( 21  is a tree . Hence D is a complementary tree dominating in 21 GG  Suppose (ii) holds. Let .)( 21 DGGVx −  Suppose .)().()( 11 DGVxeiGVx − Since DGV )( 1 is a dominating in G1, there exist DGVy  )( 1 such that ( ) 1, =txdG for some )( 1GVt  is follows that ( ) .1, 21 =yxd GG  Suppose ( )vGVx 2 for some )( 1GVv .1),().()().( 212 =− vxdeiDGVxei GG v  If Dv which is a contradiction to ( ) .2 DGVx v − Hence Dv is ( ) DGVv − 1 . In this case ( ) DGV v 2 is dominating in vG2 (𝑖. 𝑒) there exist ( ) DGVw w  2 such that .1),( 2 =wxd vG It follows that ( ) .1, 21 =wxd GG  Hence D is a dominating set in 21 GG  . Let ( )21, GGVyx  suppose ( )1, GVyx  ).( ei ( ) DGVyx −, . Since DGV )( is a complementary tree dominating set in G, and − DGV )( 1 is a tree. From this − DGGV )( 21  is a tree which contains a path x-y in .)( DGV − Suppose ( )1GVx and ( )vGVy 2 for some ( ) ( ) DGVxeiGVv − 1).( and ( ) .2 DGVy v − If vx= there exists between x-y. Suppose vx if ( ) DGVv  1 then ( ) .2 DGV v  This contradicts the fact that ( ) .02 − DGV v Then ( ) ,1 DGVv − consequently, ( ) DGV v −2 is a dominating set in vG2 ).( ei ( ) .2  DGV v Suppose ( ) .2 DGVx v  Since ( ) DGVvx − 1, and ( ) − DGV 1 contains a path with vertices .vx− Thus ( ) − DGGV 21  contains a tree with vertices .vx− Suppose ( ) yxDGVyx v − ,, 2 for some ( ).GVv If ,Dv then ( ) DGV v 2 .This contradicts the fact that ( ) .2 − DGV v Thus Dv (i.e) .)( 1 DGVv − Now there exists a path with vertices yvx ,, in ( ) .21 DGGV − Suppose ( )vGVx 2 and ( )wGVy 2 for some ( ) .,, wvGVwv  Then ( ) DGVx v − 2 and ( ) DGVy w − 2 if Dv or Dw then ( ) DGV v 2 and ( ) .2 DGV w  This contradicts the facts that ( ) − DGV v 2 and ( ) − DGV w 2 . Thus Dwv , that is ( ) ( ) ., 211 DGGVDGVwv −−  Since ( ) − DGV 1 is a tree. There is a tree with support vertices v and w in ( ) DGGV −21  .Hence ( ) − DGGV 21  is a tree. Hence D is a SNA complementary tree dominating in 21 GG  . Theorem 2.2. Let 1G and 2G be any SNA graph. Then ( ) ( ) ( )1 2 1 22 1 .SNA G G G G  − G1 is not a tree. Proof. Let .1 nG = Suppose there exist D such that: Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 169 https://internationalpubls.com ( ) ( ) ( )1 2 1 22 1 .SNA G G G G  − Theorem 2.3. Let G1be a tree and G2 be any SNA graph respectively. Then ( ) ( )1 2 1 2 .SNA G G G G = Proof. For each ( ).1GVv Let v G2 be a copy of G2 corresponding to vertex .v Further, for each ( ).1GVv Let vD be a minimum dominating set in .2 vG by definition ( )  1GVv vDD  = is a complementary tree dominating set in .21 GG  Thus ( ) ( ) ( ) ( ) 1 1 1 2 1 2 SNA v v V G v v V G G G D D D G G      = = =  Therefore, ( ) ( )1 2 1 2 .SNA G G G G  3. Challenges in Social Network Analysis To discover patterns, relationships, and structures within social networks, social network analysis (SNA) uses intricate data sets and sophisticated computational techniques [11]. Scalability, the dynamic nature of large-scale social networks, and the computational complexity of key metrics are some of the primary obstacles encountered during the analysis process. With millions of nodes and billions of edges in modern social networks, data storage, processing, and analysis present significant challenges. In these networks, the volume of data is often too much for traditional graph algorithms to handle, which results in high memory and computational costs [12]. Effective data management strategies are required due to the sheer volume of data in large social networks. Keeping and retrieving such huge amounts of data can take a lot of resources. Large-scale network analysis necessitates a lot of ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )21 2 22 22 2 2 2 12 12 222 2).( 2 Since.2)2( GG Gn GGnD GGei G G GGnD      − −= +−  +− Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 170 https://internationalpubls.com processing power. To run effectively on high-performance computing infrastructures, algorithms must be optimized [13]. Large graphs can use a lot of memory, so algorithms and data structures that use less memory are needed. Nodes and edges in social networks are always being added, changed, or taken out of sync. The dynamic nature poses several difficulties for analysis [14]: • For an accurate and current representation of the network to be maintained, algorithms must be able to handle updates in real time. • Methods based on batch processing are frequently incompatible with dynamic networks. It is necessary to use incremental algorithms that can update results based on network changes. • Understanding how organizations develop over the long haul requires transient investigation procedures that can follow and examine changes across different time focuses. Computation is required for some of SNA's most useful metrics, such as betweenness centrality and clustering coefficients. These metrics can be prohibitively expensive to calculate for massive networks [15]. requires the calculation of the shortest paths between each pair of nodes, which results in a high level of computational complexity. Involves looking at the area around each node, which can be expensive in large networks. Complex algorithms that don't scale well with network size are often used to find communities within a network. The accuracy and dependability of the analysis can be impacted by the incomplete or noisy nature of the data from social networks [16]. A few connections or connections probably won't be caught, prompting deficient charts. The network may contain inaccurate or false information, skewing the analysis's findings. To guarantee the analysis's robustness, it is essential to identify and deal with anomalies (such as outliers or unexpected changes). Privacy and ethical concerns are raised by the fact that social network data frequently contains sensitive information about individuals [17]. Maintaining user privacy necessitates ensuring that personal information is anonymized and protected. Specialists and experts should comply with moral rules to stay away from abuse of informal organization information. When handling data from social networks, it is essential to adhere to data protection laws like the GDPR. It is difficult to create effective algorithms that can adapt to the network's size. Utilizing equal and dispersed processing systems can upgrade the exhibition of diagram calculations. With lower computational costs, solutions that are close to optimal can be obtained by employing approximation methods. Using specific equipment, like GPUs, can speed up diagram calculations. • Ensuring that algorithms scale effectively as the size of the network grows. • Algorithm design must strike a balance between accuracy and computational efficiency. • Creating algorithms that are adaptable to a variety of network types and analysis tasks. The large scale and dynamic nature of contemporary social networks, the computational complexity of key metrics, and concerns regarding data quality and privacy present multiple obstacles to social network analysis [18]. Effective algorithm design, cutting-edge data structures, parallel and distributed computing, and solid data handling practices are all needed to meet these challenges. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 171 https://internationalpubls.com We'll look at optimization techniques and case studies that show how to deal with these problems in the real world in the following sections. Other results: Theorem 3.1.  𝑠𝑛𝑎 (𝑇 ∘ 𝐾1) = 𝑛. Proof. Let 𝐺 = 𝑇 ∘ 𝐾1 . Let 𝑉(𝑇) = {𝑣1, 𝑣2, . . . . . . . 𝑣𝑛} and vertex 𝑢𝑖 be the ith copy of 𝐾1 attached to the vertex 𝑣𝑖.Then 𝑉(𝐺) = {𝑣𝑖 , 𝑢𝑖/1 ≤ 𝑖 ≤ 𝑛}.Here 𝑢1, 𝑢2. . . . . . . 𝑢𝑛 are the pendant vertices of𝐺. We have pendant vertices are members of ctd-set of G[3]. Hence,𝐷 = {𝑢1, 𝑢2, . . . 𝑢𝑛} is a minimum SNA-set of 𝐺. Hence, |𝐷|   =   𝛾𝑠𝑛𝑎(𝐺) = 𝑛. Theorem 3.2. For, 𝑚 ≥ 4, then 𝛾𝑠𝑛𝑎(𝑇 ∘ 𝑃𝑚)   = 𝑛 ⌊ 𝑚 2 ⌋. Proof. Let 𝐺 = 𝑇 ∘ 𝑃𝑚. Let 𝑉(𝑇) = {𝑣1, 𝑣2, . . . . . . 𝑣𝑛} and {𝑢𝑗/1 ≤ 𝑗 ≤ 𝑚} be the vertex set of ith copy of 𝑃𝑚 is adjacent to the vertex 𝑣𝑖 in 𝑇. Therefore 𝑉(𝐺) = {𝑣𝑖/1 ≤ 𝑖 ≤ 𝑛} ∪ {𝑢𝑖𝑗/1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚}. We have 𝛾𝑠𝑛𝑎(𝑃𝑛) = 𝑛 − 2, 𝑛 ≥ 4. Therefore by choosing n copies of 𝑚 − 2 vertices of 𝑃𝑚. Let D={𝑢𝑖𝑗/1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚 − 2} which dominates all the vertices of G and ⟨𝑉(𝐺) − 𝐷⟩ is a network. Case (i). m is even Let 𝐷 = {𝑢𝑖2, 𝑢𝑖4, . . . . . . 𝑢𝑖𝑚}is a minimum ctd-set of G and〈𝑉(𝐺) − 𝐷〉 ≅ 𝑃𝑛 ∘ 𝐾𝑚 2 is a tree. Therefore |𝐷| =  𝑠𝑛𝑎 (𝐺) = 𝑛 ( 𝑚 2 ) (1) Case (ii). m is odd Let 𝐷 = {𝑢𝑖2, 𝑢𝑖4, . . . . . . . . 𝑢𝑖𝑚−1}is a minimum sna-set of G and〈𝑉(𝐺) − 𝐷〉 ≅ 𝑃𝑛 ∘ 𝐾𝑚−1 2 is a tree. Therefore |𝐷| =  𝑠𝑛𝑎 (𝐺) = 𝑛 ( 𝑚−1 2 ) (2) From (1) and (2) |𝐷| = 𝛾𝑠𝑛𝑎(𝑇 ∘ 𝑃𝑚)   = 𝑛 ⌊ 𝑚 2 ⌋ . Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 172 https://internationalpubls.com Theorem 3.3. For 𝑚 ≥ 3 then 𝛾𝑆𝑁𝐴(𝑇 ∘ 𝐶𝑚) = 𝑛 ⌈ 𝑚 2 ⌉. Proof. Take𝐺 = 𝑇 ∘ 𝐶𝑚.Let 𝑉(𝑇)   = {𝑣𝑖 ∶ 1 ≤ 𝑖 ≤ 𝑛} and )( mCV = {𝑢1, 𝑢2, . . . . . 𝑢𝑚}. Then𝑉(𝑇 ∘ 𝐶𝑚) = {𝑣𝑖: 1 ≤ 𝑖 ≤ 𝑛} ∪ {𝑢𝑖𝑗/1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚} We have𝛾𝑆𝑁𝐴(𝐶𝑛) = 𝑛 − 2[3], therefore by choosing n copies of (m-2) vertices of 𝐶𝑚.Let 𝐷 = {𝑢𝑖𝑗/1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚 − 2} which dominates all the vertices of G and ⟨𝑉(𝐺) − 𝐷⟩is a tree. Which contradicts the minimality of the sna-set. Therefore, by choosing non- adjacent vertices in n copies of 𝐶𝑚. Here two parts arise. Part (i) . m is even Let 𝐷 = {𝑢𝑖1, 𝑢𝑖3. . . . . 𝑢𝑖𝑚−1} is a minimum ctd-set of G which dominates all the vertices of G and ⟨𝑉(𝐺) − 𝐷⟩ ≅ 𝑇 ∘ 𝐾𝑚 2 is a tree. Therefore |𝐷| = 𝛾𝑐𝑡𝑑(𝐺) = 𝑛 ( 𝑚 2 ) (3) Part (ii). m is odd Let 𝐷 = {𝑢𝑖1, 𝑢𝑖3. . . . . 𝑢𝑖𝑚−2} is a minimum sna-set of G which dominates all the vertices of G and⟨𝑉(𝐺) − 𝐷⟩ ≅ 𝑇 ∘ 𝐾𝑚+1 2 is a tree. Therefore |𝐷| = 𝛾𝑠𝑛𝑎(𝐺) = 𝑛 ( 𝑚+1 2 ) (4) From (3) and (4) |𝐷| = 𝛾𝑠𝑛𝑎(𝑇 ∘ 𝐶𝑚) = 𝑛 ⌈ 𝑚 2 ⌉  where 𝑛 ≥ 2, 𝑚 ≥ 3. Theorem 3.4. For 𝑚 ≥ 4, then 𝛾𝑆𝑁𝐴(𝑇 ∘ 𝐾𝑚) = 𝑛(𝑚 − 1). Proof. Take 𝐺 = 𝑇 ∘ 𝐾𝑚. Let 𝑉(𝑇) = {𝑣𝑖/1 ≤ 𝑖 ≤ 𝑛} and 𝑉(𝐾𝑚)={𝑢1, 𝑢2, . . . . . 𝑢𝑚}.Then 𝑉(𝐺) = {𝑣𝑖/1 ≤ 𝑖 ≤ 𝑛} ∪ {𝑢𝑖𝑗/1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚}.We have 𝛾𝑆𝑁𝐴(𝐾𝑛) = 𝑛 − 2 [3]. Therefore by choosing n copies of (𝑚 − 2)vertices of 𝐾𝑚.Let 𝐷 1 = { 21,1/ − mjniu ji } which dominates all the vertices of G. But ⟨𝑉(𝐺) − 𝐷 1 ⟩ contains a cycle which contradicts the condition of ctd-set. Let  niuDD mi = − 1/1,1 which dominates all the vertices of G and ⟨𝑉(𝐺) − 𝐷⟩ ≅ 𝑇 ∘ Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 173 https://internationalpubls.com 𝐾1 is a tree. Hence,𝐷 = {𝑢𝑖𝑗/1 ≤ 𝑖 ≤ 𝑛,  1 ≤ 𝑗 ≤ 𝑚 − 1} is a minimum ctd-set of G. Therefore, |𝐷| = 𝛾𝑆𝑁𝐴(𝑇 ∘ 𝐾𝑚) = 𝑛(𝑚 − 1), 𝑛 ≥ 2, 𝑚 ≥ 4. Theorem 3.5. For 𝑚 ≥ 3, then 𝛾𝑆𝑁𝐴(𝑇 ∘ 𝑊𝑚) = 𝑛       + 2 1m . Proof. Take 𝐺 = 𝑇 ∘ 𝑊𝑚. Where T is a tree with 2n vertices .Let 𝑉(𝑇) = {𝑣𝑖/1 ≤ 𝑖 ≤ 𝑛} and 𝑉(𝑊𝑚) = {𝑐, 𝑢1, 𝑢2, … 𝑢𝑚−1} where c is the centre vertex and remaining vertices are in 1−mc .Then𝑉(𝑇 ∘ 𝑊𝑚) = {𝑣𝑖/1 ≤ 𝑖 ≤ 𝑛} ∪ {𝑐𝑖, 𝑢𝑖𝑗 : 1 ≤ 𝑖 ≤ 𝑛 ; 1 ≤ 𝑗 ≤ 𝑚 − 1} where 𝑐𝑖is the ith copy of Wm, 𝑢𝑖𝑗 is the ith copy of 𝑊𝑚 is adjacent to the vertex 𝑣𝑖 in 𝑇. Let  nicD i = 1/1 which dominates all the vertices of G and 11)( −− mCTDGV  which contradicts SNA-set. Let ( )       − == − 2 1 12 m nCTD mctd  .Hence 21 DDD = is a SNA-set of G. |𝐷| = n m n +      − 2 1       + = 2 1m n  𝑆𝑁𝐴 (𝑇 ∘ 𝑊𝑚) = 𝑛       + 2 1m . Theorem 3.6. For 𝑚1, 𝑚2 ≥ 2, 𝛾𝑆𝑁𝐴(𝑇 ∘ 𝐾𝑚1,𝑚2 ) = 𝑛 𝑚𝑖𝑛 ( )21,mm . Proof. Take 𝐺 = 𝑇 ∘ 𝐾𝑚 1,𝑚 2 .Let 𝑉(𝑇) = {𝑣𝑖: 1 ≤ 𝑖 ≤ 𝑛} and 𝑉(𝐾𝑚1,𝑚2 ) = {𝑢𝑗: 1 ≤ 𝑗 ≤ 𝑚1} ∪ {𝑤𝑗: 1 ≤ 𝑗 ≤ 𝑚2}. Then 𝑉(𝑇 ∘ 𝐾𝑚1𝑚2 ) = ⋃ 𝑣𝑖 𝑛 𝑖=1 ∪ {𝑢𝑖𝑗 : 1 ≤ 𝑖 ≤ 𝑛; 1 ≤ 𝑗 ≤ 𝑚1} ∪ {𝑤𝑖𝑗: 1 ≤ 𝑖 ≤ 𝑛; 1 ≤ 𝑗 ≤ 𝑚2} Case (i). 𝑚1 < 𝑚2 Let 𝐷 = {𝑢𝑖𝑗: 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚1} which dominates all the vertices of V(G) and 〈𝑉(𝐺) − 𝐷〉 ≅ 𝑇 ∘ 𝐾𝑚2 . Hence D is a minimum SNA-set of G. Therefore, Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 174 https://internationalpubls.com |𝐷| = 𝑛𝑚1 (5) Case (ii).𝑚2 < 𝑚1. Let 𝐷 = {𝑤𝑖𝑗: 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚2} which dominates all the vertices of 𝑉(𝐺) and 〈𝑉(𝐺) − 𝐷〉 ≅ 𝑇 ∘ 𝐾𝑚1 . Hence D is a minimum SNA-set of G. Therefore, |𝐷| = 𝑛𝑚2 (6) From (5) and (6)|𝐷| = 𝑛  𝑚𝑖𝑛(𝑚1, 𝑚2). Theorem 3.7. For m ≥ 3 ,𝛾𝑆𝑁𝐴(𝑇 ∘ 𝐾1,𝑚−1) = 𝑛. Proof. Let 𝑉(𝑇) = {𝑣1, 𝑣2, . . . . 𝑣𝑛}and 𝑉(𝐾1,𝑚−1) = {𝑐, 𝑢1, 𝑢2. . . . . . 𝑢𝑚} then 𝑉(𝑇 ∘ 𝐾1,𝑚) = {𝑣𝑖: 1 ≤ 𝑖 ≤ 𝑛} ∪ {𝑐𝑖: 1 ≤ 𝑖 ≤ 𝑛} ∪ {𝑢𝑖𝑗: 1 ≤ 𝑖 ≤ 𝑛 ; 1 ≤ 𝑗 ≤ 𝑚}. Let 𝐷 = {𝑐𝑖: 1 ≤ 𝑖 ≤ 𝑛} is a minimum SNA-set of 𝑇 ∘ 𝐾1,𝑚−1 and ⟨𝑉(𝑇 ∘ 𝐾1,𝑚−1) − 𝐷⟩ ≅ 𝑇 ∘ 𝐾𝑚−1 is a tree. Hence, |𝐷| = 𝑛 = 𝛾𝑆𝑁𝐴(𝑇 ∘ 𝐾1,𝑚−1). Theorem 3.8. For m≥5 then γSNA (T◦Tm)≤ n(m−p+1),where p≥2 be the number of pendant vertices of tree Tm. Proof. Take G=T∘Tm. Let V(T)={vi/1≤i≤n}and V(Tm)={uj/1≤j≤m}. Then V(G)=V(T)∪ V(⋃ 𝑇𝑚 𝑖𝑛 𝑖=1 ) where i mT is i t h copy of Tm is adjacent to the vertex vi in T. Let Di=V( i mT )−p which dominates all the vertices of i mT and vi in T. Therefore, D=V(T)∪Di=n(m+1−p) 4. Optimization Techniques for Algorithmic Improvements and Data Structures There are several optimization strategies that can be utilized in order to deal with the difficulties posed by large-scale and dynamic social networks [19]. The goal of these methods is to improve the efficiency, scalability, and accuracy of social network analysis. They include improvements to algorithms, cutting-edge data structures, and specialized hardware implementations. This segment investigates these advanced systems exhaustively. (i).Parallel Computing A computational problem is broken down into smaller tasks that can be done simultaneously using parallel computing. This method works best for graph algorithms, which frequently require independent and repetitive computations [20]. - Multi-threading: Concurrently using multiple CPU threads for computations the shortest path calculation, for instance, can be sped up with parallel BFS (breadth-first search). - Distributed Computing: Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 175 https://internationalpubls.com Processing large graphs on multiple machines by utilizing distributed systems and frameworks like Apache Hadoop and Apache Spark. In large-scale networks, this is useful for things like PageRank and community detection. - GPU Acceleration: Using GPUs' enormous parallelism to accelerate graph algorithms GPU-based executions of calculations like BFS, DFS (profundity first hunt), and centrality measures can altogether beat computer chip-based adaptations. (ii).Approximation Algorithms Approximation algorithms are suitable for large-scale networks where exact solutions are computationally infeasible because they offer near-optimal solutions at lower computational costs [21]. - Outlining Strategies: Utilizing information portrayals to make minimized rundowns of the diagram, which can then be utilized to appraise measurements like centrality and availability with high precision. - Sampling Methods: Using a representative subset of the network to draw conclusions about its properties. Procedures like irregular hub testing or edge inspecting can decrease the computational weight while saving key underlying properties. - Heuristic Algorithms: Using heuristics to quickly find solutions that are adequate for instance, greedy community detection algorithms are capable of effectively identifying dense subgraphs. Sub results on SNA for graph theory: Theorem 4.1. For any SNA graph G with m ≥ 2 vertices then n ≤ γSNA(T ◦ G) ≤ mn. The lower bound is attained if G K1,m(m ≥ 1) and the upper bound is attained if G mK Proof. Let V (T) = {ui/i = 1, . . . , n}and V (G) = {uj/j = 1, . . . ,m}then V (T ◦ G) = {ui: 1 ≤ i ≤ n} ∪ {uj: 1 ≤ j ≤ m}. Assume γsna(T ◦G) = nm + n. Let D be a γsna-set of T ◦ G having nm – n vertices and |V (T ◦ G) − D| = mn + n − nm + n = 2n vertices. Since G is SNA and each vertex of T is a member of sna-set. Therefore, n vertices of T which are adjacent to the vertex of n copies of G are member of ⟨V (T ◦ G) − D⟩ set. Let V (T ◦ G) − D = {ui: 1 ≤ i ≤ n} ∪ {ui1/1 ≤ i ≤ n}. Hence ⟨V (T ◦ G) − D⟩ T ◦ K1. Since G is SNA graph with m ≥ 2 vertices. Case (i).if δ(G) = 0, then G K1or mK Suppose G mK . Then γsna(T ◦ mK ) = mn. The upper bound equality hold. Suppose G K1 then γsna(T ◦ K1) = n. The lower bound equality holds. Case (ii).if δ(G) = 1, then G  Tm. Suppose G  Tm then γsna(T ◦ Tm) ≤ n(m − 2) < mn. Case (iii).δ(G) ≥ 2 Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 176 https://internationalpubls.com We have, γsna(G) ≤ n(m − 2) [3]. Suppose γsna(G) = m − 2 then G Km,Cm,Wm. Therefore γsna(T ◦Km) = n(m−1) and suppose γsna(T ◦Cm) =n       2 m < n(m − 1) < nm,γsna(T ◦Wm) = n       − 2 1m ≤ nm. Theorem 4.2. For SNA graph G with at least two vertices, γsna(T ◦G) =n, n ≥ 2 if and only if G K1,mm ≥ 2. Proof. For all graph given in the theorem, γctd(T ◦ G) = n. Conversely, Assume γsna(T ◦G) = n. Let D be a sna-set of T ◦G containing n vertices. Then |V (T ◦ G) − D| = |V (T ◦ G)| − |D| = mn + n − n = mn. Since ⟨V (T ◦ G) − D⟩ is a tree contains T. Let D = {v11, v21, . . . vn1}. Then |D| = n is possible only if one vertex of each copies of G dominate the vertices of G and vertices of T i.e., {vi1: 1 ≤ i ≤ n}is adjacent to vertices (V (G))I and uiT. Suppose vij(V (G)), i = 1, 2, . . . , n j = 1, 2, . . . ,m. Since G is SNA, hence vij’s are adjacent to each other in (V (G))i are adjacent to ui in T. But ⟨V (T ◦ G) − D⟩ is not a tree, which contradicts sna- set. Therefore vi1i = 1, 2, . . . , n is the only vertex adjacent to vij’s i = 1, 2, . . . , n j = 1, 2, . . . ,m. Hence, G  T ◦ K1,m(m ≥ 1). Applications of Graph Theory Algorithms for Social Network Analysis Proficient information structures are significant for taking care of huge diagrams, lessening memory use, and further developing access times [22]. Since these formats only store entries that are not zero in adjacency matrices, sparse graph memory usage is significantly reduced. CSR is ideal for quick row access, whereas CSC is preferable for column access [23]. Utilizing edge lists and adjacency lists in conjunction to store and traverse large graphs effectively. To facilitate quick access and manipulation, edge lists can be sorted. a library that provides sparse matrix operations-optimized building blocks for graph algorithms. To boost performance, it makes use of cutting-edge methods from linear algebra. Making effective ordering components to accelerate diagram activities, for example, search and crossing [24]. - Hash Maps: Hash maps are used to locate edges and nodes quickly. Hash maps, for instance, can be used to store node attributes or adjacency lists. - B-trees and Skip Records: Information structures that help proficient reach inquiries and updates, valuable for dynamic charts where hubs and edges are regularly added or eliminated. Because they can handle thousands of threads at once, GPUs are ideal for parallel graph processing [25]. The frameworks are for programming graph algorithms that are GPU-accelerated. Parallel versions of graph algorithms are frequently implemented with CUDA. hardware that is made just for graph processing tasks. Models incorporate the Graphcore IPU and Google's TPU, which can speed up AI Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 177 https://internationalpubls.com and chart handling responsibilities. For graph processing, customizable hardware options are provided by Application-Specific Integrated Circuits (ASICs) and Field-Programmable Gate Arrays (FPGAs). Allow for custom implementations that are quicker than general-purpose CPUs by providing flexibility and high performance for particular graph algorithms. designed specifically for use in large-scale graph processing tasks, delivering the highest levels of performance and efficiency. Numerous optimization methods can be combined to produce significant performance enhancements. Utilizing the qualities of the two computer processors and GPUs for various pieces of the diagram calculation. For instance, utilizing the GPU for parallel computation and the CPU for control flow. In a distributed computing environment, using GPU clusters to solve extremely large graph problems. Distributed GPU computation is supported by frameworks like TensorFlow and PyTorch, making it simpler to implement and scale graph algorithms. Real-time analysis of user interactions and trending topics is crucial on social media platforms like Twitter. Streamlined chart calculations are utilized to recognize persuasive clients and distinguish arising patterns. When it comes to real-time processing of the enormous volume of tweets and user interactions, GPU acceleration and parallel computing are particularly effective. By analyzing transaction networks, financial institutions employ graph-based methods to identify fraudulent activities. By processing transaction data in a timely manner, optimized algorithms enable anomaly detection. Without requiring extensive computation, suspicious patterns can be identified with the help of approximate algorithms and effective indexing methods. Understanding how diseases spread through social contacts in healthcare networks is made easier by graph theory. Public health officials can respond more quickly thanks to optimized algorithms, which make it easier to model and forecast disease outbreaks. When dealing with the large amounts of data that are generated in healthcare scenarios, distributed computing and compressed representations are absolutely necessary. A multifaceted strategy that incorporates algorithmic enhancements, sophisticated data structures, and specialized hardware implementations is required to optimize graph theory algorithms for social network analysis. Boosting graph algorithms' efficiency and scalability requires using compressed representations, approximation algorithms, and parallel computing. The practical impact of these optimizations is demonstrated by real-world applications in healthcare, social media analysis, and fraud detection. Researchers and practitioners can effectively address the difficulties of analyzing large-scale and dynamic social networks by continuing to develop and integrate these methods. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 178 https://internationalpubls.com Fig 1 social networking in friends session Fig 2 Sybil Attack in Social Networks Using Graphs Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 179 https://internationalpubls.com Fig 3 Networks via Graph theory Fig 4 Bipartite graph relation between customers and movies Fig 5 modeling of microblogs Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 180 https://internationalpubls.com Fig 6 Eigen values in social network analysis 5. Conclusion In conclusion, a reliable strategy for comprehending intricate social structures and dynamics is provided by optimizing graph theory algorithms for social network analysis. By upgrading the proficiency and versatility of these calculations, specialists and experts can all the more actually handle the enormous scope of information inborn in current interpersonal organizations. The creation of more effective algorithms for community detection, shortest path computations, and centrality measures—all of which are essential for identifying influential nodes and comprehending the overall topology of the network—are among the most significant advancements. Parallel processing, distributed computing, and machine learning integration are just a few of the cutting-edge computational methods that can significantly reduce the time complexity and computational overhead of traditional graph algorithms. In addition to enabling real-time analysis and insights, these optimizations open new possibilities for predictive modeling and intervention strategies in a variety of applications, including cybersecurity and social behavior studies. The difficulties of dynamic network analysis, in which the structure of the network changes over time, and the incorporation of multi-layered network perspectives, which simultaneously consider a variety of relationships and interactions, ought to be the primary areas of focus in future research. In addition, to guarantee the ethical use of these potent analytical tools, it is necessary to constantly address the privacy and data security implications of social network analysis. In general, the continuous development and adaptation of graph theory algorithms for social network analysis has enormous potential to improve decision-making processes and our comprehension of social systems in a variety of fields. REFERENCES [1] R.Frucht and F.Harary, “On the corona of two graphs”, Aequationes Math., Vol. 4,pp . 322–325, 1970. [2] F.Harary,“GraphTheory”, Addison Wesley, Reading Mass,1972. [3] O.Ore, “ Theory of Graphs”, Amer. Math. Soc. Colloq. Publ., V o l . 38,1962. [4] Sergio CanoyJr and Carmelito E.Go,“ Domination in the corona and join of graphs”, International Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 4s (2024) 181 https://internationalpubls.com Mathematical Forum,Vol. 6, No. 13,2011. [5] Fortunato, S. (2010). Community detection in graphs. *Physics Reports*, 486(3-5), 75-174. https://doi.org/10.1016/j.physrep.2009.11.002 [6] Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. *Journal of Statistical Mechanics: Theory and Experiment*, 2008(10), P10008. https://doi.org/10.1088/1742-5468/2008/10/P10008 [7] Brandes, U. (2001). A faster algorithm for betweenness centrality. *Journal of Mathematical Sociology*, 25(2), 163-177. https://doi.org/10.1080/0022250X.2001.9990249 [8] Newman, M. E. J. (2005). A measure of betweenness centrality based on random walks. *Social Networks*, 27(1), 39-54. https://doi.org/10.1016/j.socnet.2004.11.009 [9] Lambiotte, R., & Rosvall, M. (2012). Ranking and clustering of nodes in networks with smart teleportation. *Physical Review E*, 85(5), 056107. https://doi.org/10.1103/PhysRevE.85.056107 [10] Leskovec, J., Rajaraman, A., & Ullman, J. D. (2014). Mining of Massive Datasets (2nd ed.). Cambridge University Press. https://doi.org/10.1017/CBO9781139924801 [11] Koutra, D., Kang, U., Vreeken, J., & Faloutsos, C. (2014). VoG: Summarizing and understanding large graphs. *2014 SIAM International Conference on Data Mining (SDM)*, 91-99. https://doi.org/10.1137/1.9781611973440.11 [12] Ahmed, N. K., Neville, J., Rossi, R. A., & Duffield, N. (2017). Efficient graphlet counting for large networks. *2017 IEEE International Conference on Data Mining (ICDM)*, 1-10. https://doi.org/10.1109/ICDM.2017.20 [13] Al-Karaki, J. N., & Kamal, A. E. (2004). Routing techniques in wireless sensor networks: A survey. *IEEE Wireless Communications*, 11(6), 6-28. https://doi.org/10.1109/MWC.2004.1368893 [14] Borgatti, S. P., & Everett, M. G. (2006). A graph-theoretic perspective on centrality. *Social Networks*, 28(4), 466-484. https://doi.org/10.1016/j.socnet.2005.11.005 [15] Mondal, B.; De, K. Overview Applications of Graph Theory in Real Field. Int. J. Sci. Res. Comput. Sci. Eng. Inf. Technol. 2017, 2, 751–759. [16] Bisen, S.K. Application of Graph Theory in Transportation Networks. Int. J. Sci. Res. Manag. 2017, 5, 10–12. [17] Durand, G.; Belacel, N.; Laplante, F. Graph theory based model for learning path recommendation. Inf. Sci. 2013, 251, 10–21. [18] Kontokosta, C.E. Big Data + Big Cities: Graph Signals of Urban Air Pollution. IEEE Signal Process. Mag. 2014, 31, 130–136. [19] Liu, Y.; Safavi, T.; Dighe, A.; Koutra, D. Graph Summarization Methods and Applications: A Survey. ACM Comput. Surv. 2018, 51, 1–34. [20] Yu, Q.; Du, Y.; Chen, J.; Sui, J.; Adalē, T.; Pearlson, G.D.; Calhoun, V.D. Application of Graph Theory to Assess Static and Dynamic Brain Connectivity: Approaches for Building Brain Graphs. Proc. IEEE 2018, 106, 886–906. [21] Sporns, O. Graph theory methods: Applications in brain networks. Dialogues Clin. Neurosci. 2018, 20, 111. [22] Farahani, F.V.; Karwowski, W.; Lighthall, N.R. Application of Graph Theory for Identifying Connectivity Patterns in Human Brain Networks: A Systematic Review. Front. Neurosci. 2019, 13, 585. [23] Sahu, S.; Mhedhbi, A.; Salihoglu, S.; Lin, J.; Özsu, M.T. The ubiquity of large graphs and surprising challenges of graph processing: Extended survey. VLDB J. 2019, 29, 1–24. [24] Can, U.; Alatas, B. A new direction in social network analysis: Online social network analysis problems and applications. Phys. A Stat. Mech. Appl. 2019, 535, 122372. [25] Casas-Roma, J. An evaluation of vertex and edge modification techniques for privacy-preserving on graphs. J. Ambient. Intell. Humaniz. Comput. 2019, 11, 1–17.