Ratio Mathematica Volume 46, 2023 Degree of an edge and Platt number in signed networks Diviya K D* Anjaly Kishore† Abstract Positive labelled edges play a vital role in network analysis.The de- gree of edges in signed graphs is introduced by giving importance to positive edges incident on the end vertices of that edge. The concept of Platt number of a graph, which is the sum of degrees of its edges, is extended to signed graphs based on the degree defined. Bounds of de- gree of an edge and Platt number in certain classes of signed graphs are determined. Some characterizations on Platt number of signed graphs are also established. A model to analyse social networks us- ing degree of edges and Platt number is also proposed. Keywords: Signed graph, positive edges, negative edges, networks, information diffusion, degree of an edge, Platt number 2020 AMS subject classifications: 54A40. 1 *Department of Mathematics, Sree Narayana College Nattika, Thrissur, India. divi- yarenju@gmail.com. †Department of Mathematics, Vimala College Thrissur, Thrissur, India. anjalyk- ishor@gmail.com. 1Received on September 15, 2022. Accepted on December 15, 2022. Published on March 20, 2023. DOI: 10.23755/rm.v46i0.1061. ISSN: 1592-7415. eISSN: 2282-8214. ©Diviya K D et al. This paper is published under the CC-BY licence agreement. 91 Diviya K D and Anjaly Kishore 1 Introduction Graph Theory is a branch of Mathematics that is extensively used to math- ematically model social science which is discussed in Harary and Norman [1953]. According to Cartwright and Harary, in the paper Cartwright and Harary [1956], graphs can be used for representing relationships between persons whatever be the nature of relationships. The social relationships between individuals in soci- ety is not uniform. There may be a lot of variations in the type and intensity in the relationships between individuals. Friendship, like etc. are examples of positive relationships between two persons and enmity, indifference etc. are examples of negative relationships between them. In Graph theory, positive labelled edges can be used to represent the positive relationships and negative labelled edges can be used to represent negative relationships. If there does not exist any kind of rela- tionships between persons, it can be represented by non adjacent vertices. Such graphs that are used to represent networks, especially in social science, are called signed graphs by Harary et al. [1965]. From Acharya [1986], Zaslavsky [2012], Anchuri and Magdon-Ismail [2012] and Tang et al. [2016] we can understand that signed graphs are well studied in literature because of their easiness to represent social systems in the real world. A signed graph is a graph ∑ (G,σ) with underlying graph G(V,E) and sig- nature function σ : E → {1,−1}. Degree of an edge in an unsigned graph is the number of edges incident on the end vertices of that edge excluding it. De- gree of an edge plays a vital role in networks such as communication networks, transportation networks etc. as it indicates the influence of that edge(type of con- nection) in that particular network. In Platt [1947] the concept of Platt number is discussed and it is mainly intended to study molecular structures in Chemistry. Several characterizations related to Platt number of various graphs representing molecular structures are discussed in Belavadi and Mangam [2018]and Mahadevi et al. [2018]. Here we study these concepts in signed graphs. Information diffusion in social networks is widely studied in literature which can be seen in Guille et al. [2013], Jalali et al. [2016] and Tselykh et al. [2020]. Various models also were proposed in literature to study information diffusion and influence maximisation in social networks which was discussed in Rui et al. [2018] and Li et al. [2019]. The motivation behind the study is that signed graphs can be effectively used to represent social networks as depicted in Acharya [1985], Gionis et al. [2020] and Sun et al. [2020]. Degree of an edge can be used to interpret the strength of influence of that particular edge which represents the specified relationship in the concerned network. Hence information diffusion is possible through the edge with maximum degree. Platt number can also be used to analyse the strength of connectedness of various networks. In this paper, we extend the definition of degree of an edge and Platt number 92 Degree of an edge and Platt number in signed networks to signed graphs by giving more importance to positive labelled edges incident on the end vertices of that edge. This is done because of the extensive importance of positive edges in networks especially in social networks. Further, we find bounds on degree of an edge and Platt number in signed graphs and certain classes of signed graphs related to social networks. We then present some characerizations on the Platt number of signed graphs. Finally we propose a model to analyse networks based on degree of edges and Platt number. 2 Degree of an edge in a signed graph In this section the definition of degree of an edge, discussed in Acharya et al. [2009], is extended to signed graphs and also some of its characterizations in signed graphs are investigated. 2.1 Definition If xεV , then positive degree of x is defined as the number of positive edges incident at x and is denoted by d+(x) and negative degree of x is defined as the number of negative edges incident at x and is denoted by d−(x). The degree of x is denoted by d(x) and is given by d(x) = d+(x) +d−(x) in Acharya et al. [2009]. 2.2 Definition(Degree of an edge) Let ∑ (G,σ) be a signed graph with underlying graph G(V,E) and signature function σ : E → {1,−1}. Let xyεE where x,yεV . The degree of an edge is defined as follows d(xy) = { d+(x) + d+(y) − 1 if σ(xy) = +1 d+(x) + d+(y) if σ(xy) = −1 (1) 2.3 Example Consider the following signed graph. 93 Diviya K D and Anjaly Kishore x y z w u v -1+1 -1 -1 +1 -1 Signed graph By the definition, d(xy) = 2, d(yz) = 1, d(zw) = 1, d(wx) = 1, d(xu) = 1 and d(uv) = 1. 2.4 Bounds on degree of an edge Now, bounds on degree of an edge in certain classes of graphs are de- termined. It is obvious that the lower bound of degree of an edge in any class of graphs is 0. The upperbound of degree of an edge in certain classes of graphs are given below Class of graphs Upperbound of edge degree d(e) Pn-Path graph 3 Cn-Cycle graph 3 Wn-Wheel graph n + 1 Kn-Complete graph 2n− 3 Kp,q-Complete bipartite graph p + q − 1 Hn-Helm graph n + 3 Sn-Sunflower graph n + 4 Table 1: Upper Bound-Edge Degree The following result is on the bounds of the degree of an edge in any signed graph Proposition 2.1. For a given signed graph ∑ (G,σ) with underlying graph G(V,E) with order n ≥ 3, 0 ≤ d(e) ≤ 2n− 3 Proof. Consider a connected signed graph ∑ (G,σ). By definition of degree of an edge it is clear that d(e) ≥ 0 In order to find the upperbound of degree of an edge consider an edge e = xy where x and y are vertices of maximum degree i.e. n − 1 each and all edges on 94 Degree of an edge and Platt number in signed networks x and y are positive. In order to determine the maximum possible value of degree of an edge we assume that e is labelled positive. Now d(e) = 2(n− 1) − 1 = 2n− 3 Hence 0 ≤ d(e) ≤ 2n− 3 for any edge e in ∑ (G,σ) 3 Platt number of a signed graph The concept of Platt number was discussed in Platt [1947] and it is defined as the sum of degrees of edges of a graph as in Mahadevi et al. [2018]. Here we extend the definition of Platt number to signed graphs. Consider a signed graph ∑ (G,σ) where G(V,E) is the underlying graph and σ is the signature function. The Platt number of Σ is given by F(Σ) = ∑ xyεE(G) d(xy) (2) 3.1 Example Consider the graph given in example 2.3. Degree of edges are already calcu- lated and its Platt number is given by F(Σ) = d(xy) + d(yz) + d(zw) + d(wx) + d(xu) + d(uv) = 7 4 Bounds on Platt number In this section bounds on Platt number of certain graph classes are pro- posed. From the defintion of Platt number itself it is clear that its lowerbound is 0 and is attained in the graph in which all edges are labelled negative. The upperbound of Platt number of certain graph classes are given below. Class of graphs Upperbound of Platt number Pn-Path graph 3n− 5 Cn-Cycle graph 3n Wn-Wheel graph (n− 1)(n + 6) Kn-Complete graph n(n−1)(2n−3) 2 Kp,q-Complete bipartite graph pq(p + q − 1) Hn-Helm graph n2 + 14n Sn-Sunflower graph(n ≥ 5) n2 + 25n Table 2: Upperbound-Platt number 95 Diviya K D and Anjaly Kishore Theorem 4.1. In a connected signed graph ∑ (G,σ) with underlying graph G(V,E) and order n ≥ 2, 0 ≤ F(Σ) ≤ n(n−1)(2n−3) 2 Proof. For any signed graph ∑ (G,σ), F(Σ) ≥ 0 since d(e) ≥ 0 for any edge e in Σ. Upperbound of the degree of an edge in a signed graph is 2n − 3 and the maximum number of edges in a signed graph of order n is n(n−1) 2 . So consider the maximum possible case which is the signed graph with maximum number of edges for a given order n and with all edges are labelled positive. Here Platt num- ber is n(n−1)(2n−3) 2 . Hence for any signed graph ∑ (G,σ) 0 ≤ F(Σ) ≤ n(n− 1)(2n− 3) 2 Remark 4.1. In the above theorem, the upper bound is attained by the complete graph with all edges labelled positive. Theorem 4.2. For a connected signed graph ∑ (G,σ) of size m ≥ 2, 0 ≤ F(Σ) ≤ m2. In particular if all edges are signed positive, then 3m− 2 ≤ F(Σ) ≤ m2 Proof. It is obvious that F(Σ) ≥ 0 for any connected signed graph Σ. Now for a connected graph of given size m ≥ 2, Platt number takes its maximum value in the case of a signed graph in which all edges are labelled positive and each edge takes its maximum degree which is m. In this case F(Σ) = m2. Hence 0 ≤ F(Σ) ≤ m2 for any connected signed graph ∑ of size m ≥ 2 In the case of a connected signed graph with all edges are labelled positive and size m ≥ 2, degree of an edge takes its least value 2 which is by the edges of pendant vertices and for all other m− 2 edges the least value is 3. In this case Platt number is 3m− 2. Hence 3m− 2 ≤ F(Σ) ≤ m2 for a connected signed graph of order m ≥ 2 with all edges labelled positive. Remark 4.2. In the above theorem,the upper bound is attained by the graph K1,n−1 with all edges labelled positive and lower bound is attained by the path graph Pn with all edges labelled positive. Theorem 4.3. For a signed tree Tn of order n ≥ 3, 0 ≤ F(Tn) ≤ (n − 1)2. In particular if all edges are labelled positive, then 3n− 5 ≤ F(Tn) ≤ (n− 1)2. 96 Degree of an edge and Platt number in signed networks Proof. For a given signed tree on n vertces , the maximum degree for an edge is n − 1 which is attained when all edges are labelled positive and the maximum number of edges is n− 1. In this case the Platt number is maximum and is given by (n− 1)2. Hence 0 ≤ F(Tn) ≤ (n− 1)2 for any signed tree Tn of order n ≥ 3. When all edges are labelled positive, the minimum value of degree of an edge in a tree is 2 and as in the above theorem it is taken by edges incident on pendant vertices and for all other n − 3 edges, the minimum value is 3. In this case Platt number is given by F(Tn) = 3n−5. Hence 3n−5 ≤ F(Tn) ≤ (n−1)2 for any signed tree with all edges labelled positive. Remark 4.3. In the above theorem also, when all edges are labelled positive the upper bound is attained by the tree K1,n−1 and lower bound is attained by the tree Pn. 5 Network analysis model using degree of edges and Platt number   0 +1 −1 0 +1 −1 0 +1 0 +1 +1 0 +1 −1 0 +1 0 −1 +1 +1 −1 +1 0 +1 +1 +1 −1 +1 +1 0 0 −1 +1 0 +1 0 +1 −1 +1 +1 +1 0 +1 +1 0 +1 0 0 +1 0 −1 +1 +1 0 +1 0 +1 −1 0 +1 0 0 −1 +1 0 +1 0 −1 +1 0 +1 −1 +1 −1 0 −1 −1 0 −1 −1 0 +1 +1 +1 +1 0 +1 −1 0 +1 +1 +1 0 +1 0 +1 0 +1 +1 0   . First we calculate degree of edges in order to analyse the network as degree of an edge can be considered as a measure of the influence of that particular relation- ship in the given network. Degree of edges are given in the following table. Note that, since d(xy) = d(yx) we have filled the upper triangular part of the table. As we have mentioned in the introductory part of this paper, degree of an edge can be used to analyse social networks since degree of an edge indicates the in- fluence of that particular relationship in the corresponding network. Information diffusion in social networks is possible at its maximum through the edges, which represent relationships, with maximum influence. So information diffusion is fast through the edge with maximum degree. In this section we propose a model to analyse a network and to find the most influential relationship in that network through an example. Consider a classroom consisting of ten students. Suppose a 97 Diviya K D and Anjaly Kishore v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v1 8 10 8 9 6 8 v2 10 10 9 8 10 9 v3 10 10 10 9 9 11 v4 9 7 7 10 9 v5 9 10 v6 7 8 9 v7 5 8 v8 8 7 v9 10 v10 Table 3: Degree of edges of the network teacher needs to identify the most influential student or relationship in the class in order to implement new methods of teaching effectively in the class. First we model that class using signed graphs. Edges with signature function σ(e) = +1 represent the friendship between students and those with σ(e) = −1 represent the indifference between them and vertices without edges between them shows that there is neither a friendship nor an indifference between them. Consider the following adjacency matrix of that particular signed graph which represents the above mentioned network of the class room. From the above table it is clear that edge with maximum degree is v3v9 and is 11. Hence we can conclude that the most influential relationship in this network is between v3 and v9. So in order to make communications in that class more effective and fast or to implement new strategies effectively by the teacher it is more desirable to communicate it with either v3 or v9. Platt number of this graph is 287. We can compare different networks using this Platt number as Platt number indicates the intensity of the connectedness between individuals of that particular network. Moreover, by assigning degree of edges to corresponding edges, signed graphs can be converted to weighted graphs in which weight indicates the intensity of relationships between individuals. 6 Conclusions In this paper the definition of degree of an edge and Platt number is extended to signed graphs. Some characterizations of degree of an edge and Platt number are proposed. A model to analyse networks based on the degree of edges and Platt number is also proposed. Futher we intend to study Platt number in signed graphs by applying certain graph operations which are relevant in social networks. We 98 Degree of an edge and Platt number in signed networks also intend to study networks by converting the corresponding signed graphs in to weighted graphs. References Acharya, B. D. Acharya, M. Acharya, and D. Sinha. Characterization of a signed graph whose signed line graph is s-consistent. Bull. Malaysian Math. Sci. Soc.(2), 2009. B. D. Acharya. Applications of sigraphs in behavioral sciences. MRI Tech. Rep. No. DST/HCS/409/79, 1985. B. D. Acharya. New algebraic models of social systems. Indian J. Pure Appl. Math., 17(2):150–168, 1986. P. Anchuri and M. Magdon-Ismail. Communities and balance in signed networks: A spectral approach. In 2012 IEEE/ACM International Conference on Ad- vances in Social Networks Analysis and Mining, pages 235–242, 2012. doi: 10.1109/ASONAM.2012.48. M. M. Belavadi and T. A. Mangam. Platt number of total graphs. International Journal of Applied Mathematics, 31(5):593, 2018. D. Cartwright and F. Harary. Structural balance: a generalization of heider’s the- ory. Psychological review, 63(5):277, 1956. A. Gionis, A. Matakos, B. Ordozgoiti, and H. Xiao. Mining signed networks: Theory and applications: Tutorial proposal for the web conference 2020. In Companion Proceedings of the Web Conference 2020, pages 309–310, 2020. A. Guille, H. Hacid, C. Favre, and D. A. Zighed. Information diffusion in online social networks: A survey. ACM Sigmod Record, 42(2):17–28, 2013. F. Harary and R. Z. Norman. Graph theory as a mathematical model in social science. Number 2. University of Michigan, Institute for Social Research Ann Arbor, MI, 1953. F. Harary, R. Z. Norman, and D. Cartwright. Structural models: An introduction to the theory of directed graphs. Wiley, 1965. M. S. Jalali, A. Ashouri, Herrera-Restrepo, and H. Zhang. Information diffusion through social networks: The case of an online petition. Expert Systems with Applications, 44:187–197, 2016. 99 Diviya K D and Anjaly Kishore D. Li, W. Wang, C. Jin, J. Ma, X. Sun, Z. Xu, S. Li, and J. Liu. User recom- mendation for promoting information diffusion in social networks. Physica A: Statistical Mechanics and its Applications, 534:121536, 2019. P. Mahadevi, A. Babu, and J. B. Babujee. Platt number for some chemical graphs and general results. International Journal of Mathematics Trends and Technol- ogy(IJMTT), 2018. J. R. Platt. Influence of neighbor bonds on additive bond properties in paraffins. The Journal of Chemical Physics, 15(6):419–420, 1947. X. Rui, F. Meng, Z. Wang, G. Yuan, and C. Du. Spir: The potential spreaders involved sir model for information diffusion in social networks. Physica A: Statistical Mechanics and its Applications, 506:254–269, 2018. R. Sun, C. Chen, X. Wang, Y. Zhang, and X. Wang. Stable community detec- tion in signed social networks. IEEE Transactions on Knowledge and Data Engineering, pages 1–1, 2020. doi: 10.1109/TKDE.2020.3047224. J. Tang, Y. Chang, C. Aggarwal, and H. Liu. A survey of signed network mining in social media. ACM Computing Surveys (CSUR), 49(3):1–37, 2016. A. Tselykh, V. Vasilev, L. Tselykh, and F. A. Ferreira. Influence control method on directed weighted signed graphs with deterministic causality. Annals of Op- erations Research, pages 1–25, 2020. T. Zaslavsky. A mathematical bibliography of signed and gain graphs and allied areas. The Electronic Journal of Combinatorics, pages DS8–Dec, 2012. 100