In this paper, we investigate the theory of rough set to study graphs using the concept of orbits. Rough sets are based on a clustering criterion and we use the idea of similarity of vertices under automorphism as a criterion. We introduce indiscernibility relation in terms of orbits and prove necessary and sufficient conditions under which the indiscernibility partitions remain the same when associated with different attribute sets. We show that automorphisms of the graph $ \mathcal{G} $ preserve the indiscernibility partitions. Further, we prove that for any graph $ \mathcal{G} $ with $ k $ orbits, any reduct $ \mathcal{R} $ consists of one element from $ k-1 $ orbits of the graph. We also study the rough membership functions for paths, cycles, complete and complete bipartite graphs. Moreover, we introduce essential sets and discernibility matrices induced by orbits of graphs and study their relationship. We also prove that every essential set consists of union of any two orbits of the graph.
Citation: Imran Javaid, Shahroz Ali, Shahid Ur Rehman, Aqsa Shah. Rough sets in graphs using similarity relations[J]. AIMS Mathematics, 2022, 7(4): 5790-5807. doi: 10.3934/math.2022320
In this paper, we investigate the theory of rough set to study graphs using the concept of orbits. Rough sets are based on a clustering criterion and we use the idea of similarity of vertices under automorphism as a criterion. We introduce indiscernibility relation in terms of orbits and prove necessary and sufficient conditions under which the indiscernibility partitions remain the same when associated with different attribute sets. We show that automorphisms of the graph $ \mathcal{G} $ preserve the indiscernibility partitions. Further, we prove that for any graph $ \mathcal{G} $ with $ k $ orbits, any reduct $ \mathcal{R} $ consists of one element from $ k-1 $ orbits of the graph. We also study the rough membership functions for paths, cycles, complete and complete bipartite graphs. Moreover, we introduce essential sets and discernibility matrices induced by orbits of graphs and study their relationship. We also prove that every essential set consists of union of any two orbits of the graph.
| [1] | S. Andhalkar, B. F. Momin, Rough set theory and its extended algorithms, In: Proceedings of the second international conference on intelligent computing and control systems (ICICCS), IEEE Xplore, 2018. |
| [2] |
G. Cattaneo, An investigation about rough set theory: Some foundational and mathematical aspects, Fund. Inform., 108 (2011), 197–221. https://doi.org/10.3233/FI-2011-420 doi: 10.3233/FI-2011-420
|
| [3] |
G. Cattaneo, G. Chiaselotti, D. Ciucci, T. Gentile, On the connection of hypergraph theory with formal concept analysis and rough set theory, Inform. Sciences, 330 (2016), 342–357. https://doi.org/10.1016/j.ins.2015.09.054 doi: 10.1016/j.ins.2015.09.054
|
| [4] |
J. Chen, J. Li, An application of rough sets to graph theory, Inform. Sciences, 201 (2012), 114–127. https://doi.org/10.1016/j.ins.2012.03.009 doi: 10.1016/j.ins.2012.03.009
|
| [5] | G. Chiaselotti, D. Ciucci, T. Gentile, Simple undirected graphs as formal contexts, Formal concept analysis, Lecture Notes in Computer Science, Springer, 9113 (2015), 287–302. https://doi.org/10.1007/978-3-319-19545-2_18 |
| [6] | G. Chiaselotti, D. Ciucci, T. Gentile, F. Infusino, Rough set theory applied to simple undirected graphs, In: Rough sets and knowledge technology, Lecture Notes in Computer Science, Springer, 9436 (2015), 423–434. https://doi.org/10.1007/978-3-319-25754-9_37 |
| [7] |
G. Chiaselotti, T. Gentile, F. Infusino, P. A. Oliverio, The adjacency matrix of a graph as a data table: A geometric perspective, Ann. Mat. Pur. Appl., 196 (2017), 1073–1112. https://doi.org/10.1007/s10231-016-0608-1 doi: 10.1007/s10231-016-0608-1
|
| [8] |
G. Chiaselotti, D. Ciucci, T. Gentile, Simple graphs in granular computing, Inform. Sciences, 340-341 (2016), 279–304. https://doi.org/10.1016/j.ins.2015.12.042 doi: 10.1016/j.ins.2015.12.042
|
| [9] |
F. Catanzariti, G. Chiaselotti, F. G. Infusino, G. Marino, Object similarity measures and Pawlak's indiscernibility on decision tables, Inform. Sciences, 539 (2020), 104–135. https://doi.org/10.1016/j.ins.2020.05.030 doi: 10.1016/j.ins.2020.05.030
|
| [10] | D. Chitcharoen, P. Pattaraintakorn, Towards theories of fuzzy set and rough set to flow graphs, In: IEEE international conference on fuzzy systems (IEEE World Congress on Computational Intelligence), 2008, 1675–1682. |
| [11] |
P. Honko, Relational pattern updating, Inform. Sciences, 189 (2012), 208–218. https://doi.org/10.1016/j.ins.2011.12.004 doi: 10.1016/j.ins.2011.12.004
|
| [12] |
P. Honko, Association discovery from relational data via granular computing, Inform. Sciences, 234 (2013), 136–149. https://doi.org/10.1016/j.ins.2013.01.004 doi: 10.1016/j.ins.2013.01.004
|
| [13] |
B. Huang, Y. Zhuang, H. Li, D. Wei, A dominance intuitionistic fuzzy-rough set approach and its applications, Appl. Math. Model., 37 (2013), 7128–7141. https://doi.org/10.1016/j.apm.2012.12.009 doi: 10.1016/j.apm.2012.12.009
|
| [14] |
M. Hu, E. C. C. Tsang, Y. Guo, D. Chen, W. Xu, A novel approach to attribute reduction based on weighted neighborhood rough sets, Knowl.-Based Syst., 220 (2021), 106908. https://doi.org/10.1016/j.knosys.2021.106908 doi: 10.1016/j.knosys.2021.106908
|
| [15] |
X. Kang, D. Li, S. Wang, K. Qu, Formal concept analysis based on fuzzy granularity base for different granulations, Fuzzy Sets Syst., 203 (2012), 33–48. https://doi.org/10.1016/j.fss.2012.03.003 doi: 10.1016/j.fss.2012.03.003
|
| [16] | T. Y. Lin, Data mining: Granular computing approach, In: Methodologies for knowledge discovery and data mining, Lecture Notes in Computer Science, Springer, 1574 (1999), 24–33. https://doi.org/10.1007/3-540-48912-6_5 |
| [17] |
T. Y. Lin, Data mining and machine oriented modeling: A granular approach, Appl. Intell., 13 (2000), 113–124. https://doi.org/10.1023/A:1008384328214 doi: 10.1023/A:1008384328214
|
| [18] |
F. L. Liu, B. W. Zhang, D. Ciucci, W. Z. Wu, F. Min, A comparison study of similarity measures for covering-based neighborhood classifiers, Inform. Sciences, 448-449 (2018), 1–17. https://doi.org/10.1016/j.ins.2018.03.030 doi: 10.1016/j.ins.2018.03.030
|
| [19] | H. Midelfart, J. Komorowski, A rough set framework for learning in a directed acyclic graph, In: Rough sets and current trends in computing, Lecture Notes in Computer Science, Springer, 2475 (2002), 144–155. |
| [20] |
W. Pan, J. Yi, Y. San, Rough set theory and its application in the intelligent systems, 2008 7th world congress on intelligent control and automation, 2008, 3706–3711. https://doi.org/10.1109/WCICA.2008.4593519 doi: 10.1109/WCICA.2008.4593519
|
| [21] |
M. S. Pathan, Z. Jianbiao, D. John, A. Nag, S. Dev, Identifying stroke indicators using rough sets, IEEE Access, 8 (2020). https://doi.org/10.1109/ACCESS.2020.3039439 doi: 10.1109/ACCESS.2020.3039439
|
| [22] | Z. Pawlak, Rough sets: Theoretical aspects of reasoning about data, Kluwer Academic Publishers, 1991. https://doi.org/10.1007/978-94-011-3534-4 |
| [23] |
Z. Pawlak, A. Skowron, Rough sets and boolean reasoning, Inform. Sciences, 177 (2007), 41–73. https://doi.org/10.1016/j.ins.2006.06.007 doi: 10.1016/j.ins.2006.06.007
|
| [24] |
Z. Pawlak, A. Skowron, Rough sets: Some extensions, Inform. Sciences, 177 (2007), 28–40. https://doi.org/10.1016/j.ins.2006.06.006 doi: 10.1016/j.ins.2006.06.006
|
| [25] | Z. Pawlak, A. Skowron, Rudiments of rough sets, Inform. Sciences, 177 (2007), 3–27. |
| [26] |
A. Pedrycz, K. Hirota, W. Pedrycz, F. Dong, Granular representation and granular computing with fuzzy sets, Fuzzy Sets Syst., 203 (2012), 17–32. https://doi.org/10.1016/j.fss.2012.03.009 doi: 10.1016/j.fss.2012.03.009
|
| [27] |
T. Qiu, X. Chen, Q. Liu, H. Huang, Granular computing approach to finding association rules in relational database, Int. J. Intell. Syst., 25 (2010), 165–179. https://doi.org/10.1002/int.20394 doi: 10.1002/int.20394
|
| [28] | A. Skowron, C. Rauszer, The discernibility matrices and functions in information systems, In: Intelligent decision support, Springer, 11 (1992), 331–362. https://doi.org/10.1007/978-94-015-7975-9_21 |
| [29] |
J. Tang, K. She, W. Zhu, Matroidal structure of rough sets from the viewpoint of graph theory, J. Appl. Math., 2012 (2012), 1–27. https://doi.org/10.1155/2012/973920 doi: 10.1155/2012/973920
|
| [30] |
C. Wang, D. Chen, A short note on some properties of rough groups, Comput. Math. Appl., 59 (2010), 431–436. https://doi.org/10.1016/j.camwa.2009.06.024 doi: 10.1016/j.camwa.2009.06.024
|
| [31] |
S. Wang, Q. Zhu, W. Zhu, F. Min, Equivalent characterizations of some graph problems by covering-based rough sets, J. Appl. Math., 2013 (2013), 1–7. https://doi.org/10.1155/2013/519173 doi: 10.1155/2013/519173
|
| [32] | J. Wang, W. Zhu, An approach to covering-based rough sets through bipartite graphs, In: IEEE international conference on fuzzy systems (FUZZ-IEEE), IEEE, 2014, 1213–1218, https://doi.org/10.1109/FUZZ-IEEE.2014.6891666 |
| [33] |
W. Wu, Y. Leung, J. Mi, Granular computing and knowledge reduction in formal contexts, IEEE T. Knowl. Data En., 21 (2009), 1461–1474. https://doi.org/10.1109/TKDE.2008.223 doi: 10.1109/TKDE.2008.223
|
| [34] | Y. Y. Yao, On modeling data mining with granular computing, In: 25th annual international computer software and applications conference, COMPSAC, 2001 (2001), 638–643. https://doi.org/10.1109/CMPSAC.2001.960680 |
| [35] | J. T. Yao, Y. Y. Yao, A granular computing approach to machine learning, FSKD, 2 (2002), 732–736. |
| [36] | L. A. Zadeh, Fuzzy set and information granularity, Adv. Fuzzy Syst. Appl. Theory, 11 (1996), 433–448. |
Figures(3) / Tables(1)
Imran Javaid, Shahroz Ali, Shahid Ur Rehman, Aqsa Shah. Rough sets in graphs using similarity relations[J]. AIMS Mathematics, 2022, 7(4): 5790-5807. doi: 10.3934/math.2022320
DownLoad: