- Надежная сетевая субмодульная максимизация последовательностей (arXiv)
Автор: Цихао Ши, Бинъян Фу, Цань Ван, Цзявэй Чен, Шэн Чжоу, Янь Фэн, Чунь Чен.
Аннотация: В этой статье мы изучаем \underline{R}obust\underline{o}оптимизацию для \underline{se}quence \underline{Net}worked\underline{s}субмодулярной задачи максимизации (RoseNets). Мы переплетаем робастную оптимизацию с последовательной сетевой субмодульной максимизацией. Элементы связаны ориентированным ациклическим графом, а целевая функция субмодулярна не на элементах, а на ребрах графа. В таком сетевом субмодульном сценарии влияние удаления элемента из последовательности зависит как от его положения в последовательности, так и в сети. Это делает существующие надежные алгоритмы неприменимыми. В этой статье мы делаем первый шаг к изучению проблемы RoseNets. Мы разрабатываем надежный жадный алгоритм, который устойчив к удалению произвольного подмножества выбранных элементов. Коэффициент аппроксимации алгоритма зависит как от количества удаляемых элементов, так и от топологии сети. Далее мы проводим эксперименты с реальными приложениями рекомендаций и прогнозирования ссылок. Экспериментальные результаты демонстрируют эффективность предложенного алгоритма.
2. Максимизация прибыли в социальных сетях и немонотонная DR-субмодулярная максимизация (arXiv)
Автор: Шуян Гу, Чуанген Гао, Цзюнь Хуан, Вэйли Ву.
Аннотация: В работе исследуется максимизация немонотонной DR-субмодулярной функции на целочисленной решетке. Функциям над целочисленной решеткой было определено субмодулярное свойство, аналогичное субмодулярности функций множества. DR-субмодулярность — это еще одна расширенная субмодульная концепция для функций над целочисленной решеткой, которая отражает свойство убывающей отдачи. Такие функции находят множество применений в машинном обучении, социальных сетях, беспроводных сетях и т. д. Методы максимизации субмодульной функции множества могут быть применены к максимизации DR-субмодулярной функции, например, двойной жадный алгоритм имеет коэффициент аппроксимации 1/2, у которого время работы O(nB), где n — размер наземного множества, B — целочисленная граница координаты. В нашем исследовании мы разрабатываем 1/2-приближенный алгоритм двойного жадного бинарного поиска и доказываем, что его временная сложность составляет O(nlogB), что значительно сокращает время выполнения. В частности, мы рассматриваем ее применение к задаче максимизации прибыли в социальных сетях с двудольной моделью, целью которой является максимизация чистой прибыли, полученной от деятельности по продвижению продукта, которая представляет собой разницу усиления влияния и стоимости продвижения. Доказано, что целевая функция является DR-субмодулярной на целочисленной решетке. Мы применяем алгоритм бинарного поиска с двойной жадностью к этой задаче и проверяем эффективность
