Combinatorial complexity of the signature of a natural tiling

Abstract

An additive model has been developed for calculating the combinatorial (Shannon-like) complexity of a signature of the natural tiling, which is used to describe the topological properties of micro- and mesoporous materials, in particular, zeolites. To calculate the complexity of this type, a Python program code has been compiled. The code was tested for tilings of a zeolite type. Correlations of the calculated complexity of a signature of the tiling and the combinatorial complexity of the tiling-generating structure were found.

Full Text

Введение

Информационная энтропия H по Шэннону [1], она же шэнноновская, или комбинаторная, сложность, обычно выражается в битах и в таком случае имеет вид

$H=-\sum _{i=1}^s{p}_i{\log }_2{p}_i$, (1)

где p_i = m_i/m – доля m_i элементов i-го вида в дискретном множестве из m элементов, каждый элемент которого отнесен к одному из s видов, $\sum _{i=1}^s{p}_i=1$. Комбинаторная сложность используется в химии как мера сложности молекулярных ансамблей [2], в том числе дендримеров [3], и ее изменения при химических превращениях [4–7], а в кристаллографии как мера сложности кристаллических структур [8–17] и химических составов [18], а также систем порождающих операций кристаллографических групп [19] и систем опорных контактов в кристаллической структуре [20]. В минералогии информационную энтропию использовал академик Н.П. Юшкин для оценки сложности распределения минералов по сингониям [21]. Применению информационной энтропии в минералогии и кристаллографии также посвящен миниобзор Ю.Л. Войтеховского [22].

Комбинаторная сложность относится к более широкому классу индексов видового разнообразия, называемому числами Хилла, поскольку является числом Хилла первого порядка [23]. В кристаллографии числа Хилла можно использовать для оценки неравномерности распределений записей в структурных банках данных по кристаллографическим таксонам, таким как сингонии, кристаллические классы, пространственные группы [24]. Видовое разнообразие объектов неживой природы имеет некоторые сходства с разнообразием биологических видов [25].

В настоящей работе исследована комбинаторная сложность сигнатуры натурального тайлинга [26]. Под тайлингом понимается нормальное (грань к грани) разбиение пространства на тайлы – обобщенные, не обязательно выпуклые полиэдры, в которых каждая вершина инцидентна двум или более вершинам, а грани могут быть криволинейными [27]. Всякому тайлингу соответствует некоторая сетка, образованная вершинами и ребрами. Натуральным называют тайлинг, отвечающий следующим условиям: симметрия тайлинга совпадает с симметрией соответствующей ему сетки; гранями тайла являются сильные кольца (циклы, не являющиеся суммой нескольких циклов меньшего размера); все сильные кольца сетки, кроме принадлежащих граням, имеют пересечения, т.е. общие внутренние точки; если в соответствии с предыдущими пунктами возможны разные тайлинги, то путем объединения тайлов друг с другом строят один тайлинг. Таким образом, если для данной сетки натуральный тайлинг вообще существует, то только один. Поиск натурального тайлинга в общем случае нетривиален, но достаточно давно реализован в программном комплексе ToposPro [28]. Для тайлов принято использовать гранный символ вида [A^a.B^b...], который означает наличие у тайла a A-угольных, b B-угольных граней, A < B < ... . На рис. 1 изображен натуральный тайл [4³⁶] структуры пирохлора. Тайлинг принято обозначать сигнатурой, показывающей cоотношение тайлов, например, запись 2[3⁴] + [3⁸] означает тетраэдрические [3⁴] и октаэдрические [3⁸] тайлы в соотношении 2 : 1.

Рис. 1. Тайл [4³⁶] одноименного натурального тайлинга структуры пирохлора Ca₂Nb₂O₆F.

Метод

Для сложения комбинаторной сложности от нескольких источников информации простая аддитивность подходит только в том случае, если источники информации независимы [29]. Например, если две подсистемы одной системы изолированы друг от друга, т.е. разделены в пространстве и не обмениваются массой и энергий. Но если подсистемы взаимозависимы, как это всегда бывает с подструктурами одной кристаллической структуры [17], то должна выполняться сильная аддитивность: помимо слагаемых, отвечающих отдельным подсистемам, в сумму включается дополнительное слагаемое, которое учитывает прирост информации за счет смешивания подсистем. В работах Сабирова (например, [30]) такое дополнительное слагаемое называется эмерджентным параметром. Принципы разложения комбинаторной сложности дискретных мультимножеств на вклады отдельных множеств с эмерджентным параметром были подробно рассмотрены в [13].

Применим этот подход к сигнатуре натурального тайлинга, записанной в стандартном виде

$\begin{array}{c}{k}_1\left[A_1{{}^a}^1.B_1{{}^b}^1\mathrm{...}\right]+k_2\left[A_2{{}^a}^2.B_2{{}^b}^2\mathrm{...}\right]+\\ +\dots +k_n\left[A_1{{}^a}^n.B_1{{}^b}^n\mathrm{...}\right],\end{array}$ (2)

где k₁:k₂:…:k_n – простейшее целочисленное соотношение n тайлов разного сорта. Совокупность граней тайла i-го сорта (i = 1, …, n) представляет собой мультимножество Φ_i = {(A_i, a_i), (B_i, b_i), …}. Комбинаторная сложность такого мультимножества по определению (1) равна

$\begin{array}{c}{H}_{\text{tile},i}=-\frac{a_i}{a_i + b_i + \dots }{\log }_2\frac{a_i}{a_i + b_i + \dots }-\\ -\frac{b_i}{a_{i }+ b_i + \dots }{\log }_2\frac{b_i}{a_i + b_i + \dots }-\dots .\end{array}$ (3)

Совокупность k_i граней тайлов i-го сорта представляет собой мультимножество {(A_i, k_ia_i), (B_i, k_ib_i), …}, имеющее такую же комбинаторную сложность H_tile,i. Складывая значения H_tile,i с учетом соотношения между тайлами по правилу сильной аддитивности [13], получаем

$H_{\text{tiling}}={\sum }_{i=1}^n{w}_i{H}_{\text{tile},i}+H\left(w_1,w_2,\dots ,w_n\right)$, (4)

$w_i=\frac{k_i{\phi }_i}{\sum k_i{\phi }_i}$, (5)

$H\left(w_1,w_2,\dots ,w_n\right)=-{\sum }_{i=1}^n{w}_i{\log }_2{w}_i$, (6)

где φ_i = (a_i + b_i +…) – число граней в i-м тайле, w_i – весовые множители, определяющие вклад H_tile,i в общую сложность тайлинга H_tiling. Сложность, рассчитываемая по формуле (6), является эмерджентным параметром [30]. Как следует из свойств сильной аддитивности [13], H_tiling является комбинаторной сложностью мультимножества

$\Phi =\left\{{\cup }_{i=1}^n\left\{\left(A_i,a_i\right),\left(B_i,b_i\right),\dots \right\}\right\}.$ (7)

Поскольку каждая грань тайлинга принадлежит ровно двум тайлам, в мультимножество Φ она включена дважды, однако это никак не влияет на распределение граней по размерам и не искажает стехиометрию тайлинга. Единицей измерения H_tile,i и H_tiling является бит/грань. При умножении H_tiling на общее число граней в сигнатуре тайлинга получается общая комбинаторная сложность сигнатуры (бит/сигнатура):

$H_{\text{tiling,tot}}=H_{\text{tiling}}\sum k_i{\phi }_i$. (8)

В табл. 1 представлен код на языке Python, позволяющий рассчитать значения H_tiling и H_tiling,tot для сколь угодно большого списка сигнатур, записанных в столбце файла с таблицей формата MS Excel. Столбец таблицы не должен иметь заголовка, формат сигнатуры (2) точно такой же, как в выдаче программы ToposPro [28] при построении тайлинга, например, “2[3^4] + [3^8]”. По умолчанию программа обращается к исходным данным по адресу C:\tilings\input.xlsx и создает в той же папке файл с именем input_with_entropies.xlsx, в котором рядом со столбом сигнатур записаны два столбца (тоже без заголовков) с рассчитанными значениями H_tiling и H_tiling,tot соответственно.

Таблица 1. Код для расчета значений H_tiling и H_tiling,tot

import pandas as pd from collections import Counter import numpy as np # Load the Excel file without headers file_path = 'C:/tilings/input.xlsx' df = pd.read_excel(file_path, header=None) # Function to transform the expression def transform_expression(expression): def expand_term(term): term = term.strip() if term[0].isdigit(): coefficient, inner = term.split('[', 1) inner = '[' + inner expanded_inner = expand_single_term(inner) expanded_inner_list = expanded_inner.strip('[]').split(',') return f"[{','.join(expanded_inner_list * int(coefficient))}]" else: return expand_single_term(term) def expand_single_term(term): term = term.strip('[]') if '.' in term: factors = term.split('.') expanded_factors = [] for factor in factors: if '^' in factor: base, exp = factor.split('^') base = base.strip() exp = int(exp.strip()) expanded_factors.extend([base] * exp) else: expanded_factors.append(factor.strip()) return f"[{','.join(expanded_factors)}]" elif '^' in term: base, exp = term.split('^') base = base.strip() exp = int(exp.strip()) return f"[{','.join([base] * exp)}]" else: return f"[{term.strip()}]" def modify_output(output): parts = output.split('+') all_values = [] for i, part in enumerate(parts): if part.startswith('[') and part.endswith(']'): inner_content = part[1:-1].split(',')

indexed_content = [f"{value.strip()}{i + 1}" for value in inner_content] all_values.extend(indexed_content) return f"[{','.join(all_values)}]" parts = expression.split('+') expanded_parts = [expand_term(part.strip()) for part in parts] final_output = '+'.join(expanded_parts) return modify_output(final_output) # Function to calculate Shannon entropy def calculate_shannon_entropy(numbers): counts = Counter(numbers) total_count = sum(counts.values()) probabilities = [count / total_count for count in counts.values()] entropy = -sum(p * np.log2(p) for p in probabilities if p > 0) return entropy # Processing each expression and calculating entropy def process_expression(expression): output = transform_expression(expression) output_numbers = list(map(int, output.strip('[]').split(','))) entropy = calculate_shannon_entropy(output_numbers) total_numbers = len(output_numbers) weighted_entropy = entropy * total_numbers return entropy, weighted_entropy # Clean and sanitize the expression input if necessary def clean_expression(expression): expression = expression.replace(']"', ']').replace('"', ʹʹ).strip() return expression # Apply cleaning and process the expressions in the first column df[0] = df[0].apply(clean_expression) df[['Entropy', 'Weighted Entropy']] = df[0].apply(lambda x: pd.Series(process_expression(x))) # Save the updated DataFrame to the same file, adding the Entropy and Weighted Entropy columns output_file_path = 'C:/tilings/input_with_entropies.xlsx' df.to_excel(output_file_path, index=False, header=False) print(f"Processed entropies saved to {output_file_path}")

Метод опробован на массиве сигнатур натуральных тайлингов цеолитного типа, представленного в сопроводительных материалах к пионерской работе [31] и насчитывавшего на тот момент 194 сигнатуры. Также был проведен поиск ранговой (по Спирмену) и линейной (по Пирсону) корреляций H_tiling и H_tiling,tot с уже известными индексами сложности цеолитных каркасов, в частности с комбинаторной сложностью по С.В. Кривовичеву I_G (бит на вершину каркаса) и I_G,tot (бит на приведенную ячейку) (по известным данным для 201 каркаса [32]), с конфигурационной сложностью H_conf (бит на степень свободы) и H_conf,tot (бит на приведенную ячейку) (по ранее полученным данным для 242 каркасов [33]), а также с числом классов симметрично-эквивалентных ребер в каркасе eʹʹ. Для поиска корреляций использовали только те каркасы, которые входили в каждый из трех массивов структур [31–33], за исключением разупорядоченных каркасов (рефкоды *BEA, *MRE и *STO в банке данных цеолитных структур [34]). Таким образом, анализировали данные по 191 каркасу.

Результаты и их обсуждение

В табл. 2 представлены коэффициенты корреляции индексов сложности для каркасов цеолитного типа и соответствующих им натуральных тайлингов. Из этих данных видно, что все тестированные пары индексов положительно коррелированы. Для случайной выборки объемом N = 191 p-уровню значимости p < 0.05 отвечает коэффициент корреляции больше 0.142; таким образом, все обнаруженные корреляции статистически значимы. Слабее всего коррелированы H_tiling,tot и eʹʹ; H_tiling средне коррелирует c другими индексами, в том числе I_G (рис. 2а); корреляцию H_tiling,tot с I_G,tot (рис. 2б) и H_conf,tot можно считать сильной. Коэффициент ранговой корреляции во всех случаях, кроме тех, в которых один из индексов eʹʹ, оказался меньше коэффициента линейной корреляции, что нетрудно объяснить одинаковой логарифмической зависимостью соответствующих индексов от некоторых, пусть и разных, структурных параметров. Как показало сравнительное исследование серии структур Hg-содержащих минералов и их синтетических аналогов, все использующиеся сегодня в кристаллографии индексы сложности в той или иной мере коррелированы друг с другом [35].

Таблица 2. Корреляции индексов сложности цеолитных каркасов и тайлингов

Индекс	Тип корреляции	IG, бит/вершина	Hconf, бит/с.с.	eʹʹ
Htiling, бит/грань	Линейная	0.690	0.670	0.601
	Ранговая	0.653	0.633	0.640
Индекс	Тип корреляции	IG,tot, бит/яч.	Hconf,tot, бит/яч.	eʹʹ
Htiling,tot, бит/сигнатура	Линейная	0.886	0.827	0.426
	Ранговая	0.779	0.774	0.615

Примечание. с.с. – степень свободы.

Рис. 2. Диаграмма рассеяния H_tiling и I_G (а), H_tiling,tot и I_G,tot (б) для каркасов цеолитного типа.

Самым сложным в исследованной выборке оказался тайлинг каркаса PAU (H_tiling,tot = 2928.3 бит/сигнатура), обладающего и наибольшим значением I_G,tot = 4763.5 бит/яч. В то же время еще более сложный каркас SFV (I_G,tot = 19557.6 бит/яч.) [32] в исследованную выборку не попал. Самым простым оказался тайлинг каркаса ABW (H_tiling,tot =9.5 бит/сигнатура), в то время как самый простой каркас – содалитовый (SOD, I_G,tot = 16.5 бит/яч. [32]). Тайлинги, как и каркасы, можно классифицировать по классу сложности [36]: очень простые (0–20 бит/сигнатура), простые (20–100), средней сложности (100–500), сложные (500–1000) и очень сложные (более 1000). Больше 80% тайлингов простые или средней сложности (рис. 3).

Рис. 3. Доля натуральных тайлингов разного класса сложности для каркасов цеолитного типа.

Натуральные тайлинги позволяют строить маршруты миграции катионов по пустотам каркаса и прогнозировать ионную проводимость, поэтому они имеют важное значение не только для каркасов цеолитного типа, но и для “антицеолитных” [37] катионных каркасов [38], а также для смешанных тетраэдрических (TT) каркасов, например, в структурах боро- [39] и бериллофосфатов [40], и даже для гетерополиэдрических MT-каркасов, например, в структурах эвдиалита [41], алюодита [42], келдышита [43], минералов группы колумбита [44], лабунцовита [45], в структурах синтетических германатов [46], ванадатов [47], молибдатов [48]. Расчет комбинаторной сложности по С.В. Кривовичеву для любого каркаса легко провести в пакете программ ToposPro [28], расчет дополнительных индексов, таких как конфигурационная сложность по Хорнфеку, возможен с помощью Python-приложения crystIT [15]. Однако, не имея cif-файла со структурными данными, провести такие расчеты невозможно. Для расчета комбинаторной сложности сигнатуры натурального тайлинга, наоборот, требуются не структурные данные, а только сигнатура тайлинга. Поэтому этот индекс сложности легко использовать в экспертных системах, не привязанных непосредственно к структурным данным. Исследователь, не являющийся специалистом в кристаллографии, может рассчитать этот индекс для серии соединений просто по списку сигнатур в литературном источнике.

Автор выражает благодарность за помощь С.М. Аксенову (КНЦ РАН), а также коллективу Международного научного-исследовательского центра по теоретическому материаловедению (г. Самара, Россия) за научный семинар, в результате которого родилась идея настоящей работы.

Работа выполнена по госзаданию Института геохимии и аналитической химии им. В.И. Вернадского РАН.