Search

Social media platforms play a crucial role in regulating public discourse. Recognizing the importance of understanding this complex phenomenon a large body of research has been published in attempts to model how information spreads within these platforms. These models are termed information propagation models. The majority of the existing information propagation models attempt to capture the causal relationship between to two information spreading events through modeling the probabilities of information transmission between the two users or through capturing the temporal correlations that exist between the events. While these models have been successful in the past, they fail to capture the various properties that have emerged in the recent past. One emerging property that has been presented in the recent analysis is the role the content of information plays in regulating the patterns of information spread. Specifically, social scientists believe that in the presence of large amounts of information, users tend to interact with items that help confirm their own views. This thesis explores a possible method to incorporate user-specific and event-specific features to existing information propagation models by scaling the edge parameters. Through modeling the scaling factors to capture the phenomena of selective exposure due to confirmation bias, we showcase the ability of our approach to capturing complex social dynamics. Through experiments on both synthetic and real-world datasets, we validate the advantages that could be gained over the existing models. The presented approach exhibits clearly visible performance gains on the network recovery task and performed competitively against the baselines.

Traditional clustering algorithms are popular for data analysis. However, by nature, they are designed for static objects. There are many applications where objects change their states over time. If to apply traditional clustering methods on every timestamp, this may produce totally different clusters on each timestamp. Instead, it would be preferable to obtain clusters smoothly evolving over time. Starting with Chakrabarti et al. \cite{Chakrabarti} in 2006, the era of dynamic clusters came to the world. Since then, evolutionary versions of clusters for popular algorithms were designed: Kmeans, hierarchical, spectral, DBSCAN. They assume that the algorithm cost function consists of a traditional algorithm cost and a temporal smoothness. Then Xu et al. \cite{AdaptiveEvolutionary} proposed an adaptive framework where smoothing was applied to a proximity matrix followed by static clustering. In the thesis, we compare the performance of the traditional algorithms Kmeans, spectral and DBSCAN with their evolutionary and adaptive modifications. For the experiments, two datasets were chosen: a synthetic, generated from four Gaussian distributions and simulated four seasons, and a Foursquare, with six seasons for venues in San Francisco. The criteria for performance evaluation are clustering goodness and smoothness between consecutive timestamps. Also, the similarity between clustering results was estimated. For the synthetic data, although the adaptive and evolutionary algorithms show best values, the traditional Kmeans and spectral algorithms differ from them neglectfully. This means there is no need to apply sophisticated algorithms. The results on the Foursquare data show that the evolutionary spectral versions perform better than the other algorithms taking into account a goodness-smoothness trade-off.

Customer Churn, also known as customer attrition occurs when customer quit using the product or stops doing business with the company. The companies are always interested in identifying those customers as customer acquisition is costly than customer retention. This thesis attempts to predict the churners using machine learning models in an invoicing software made by Isolta Oy. The actions performed by the user while using the invoicing software are tracked and stored in the data store. The data is then retrieved and cleaned for further processing. Exploratory data analysis, transformations and aggregations are performed on data to make it ready for applying machine learning models. The machine learning algorithms used in this thesis are Random Forest, K-nearest Neighbor, XGBoost and Decision Trees with boosting. XGBoost has better prediction results as compared to the other three algorithms with accuracy up to 77% and f-score of 0.77.

This Master's thesis studies methods for detecting malware while adapting to how malware change over time. Malware detection methods are necessary to defend against cyber attacks, which could otherwise compromise information systems that are integral in the daily lives of everyone living in modern societies. Machine learning models have been shown to be effective in classifying files as either malicious or benign. However, malware and other software are constantly evolving, which makes classifiers unable to learn what malware in the future will be like. Therefore, methods are required for adapting to this concept drift in malware detection. In this thesis, we compare three different methods called retrain, threshold, and hybrid that update the classifier to adapt to changes in the data over time. First, we create a classifier for detecting if a Windows portable executable file is malicious or benign. We use a dataset of 61466 files consisting of 19648 known malware and 41818 clean files. The classifier uses features that are extracted using static analysis without executing the files. To choose which classifier to use in malware detection, we compare random forest, gradient boosted decision trees, neural network, and support vector machines. Gradient boosted decision trees achieve the highest accuracy and AUC, and using a random forest for selecting most important features reduces the training time of the model. This classifier achieves an accuracy of 98.7\% when using cross-validation to evaluate the model. In contrast, when using temporally ordered files, the classifier has an accuracy of 96.7\% showing the presence of concept drift in malware detection. Each of the proposed retrain, threshold, and hybrid methods improve the accuracy of the classifier by adapting to concept drift. The best performing method is hybrid, which is a combination of the two other methods. This method is able to correctly classify 98.5\% of previously unseen files yielding a significant, Tämä diplomityö tutkii menetelmiä haittaohjelmien tunnistamiseksi ja haittaohjelmissa tapahtuviin muutoksiin mukautumiseksi. Haittaohjelmien tunnistaminen on tärkeä tapa puolustautua kyberhyökkäyksiltä, jotka voisivat muutoin vaarantaa tärkeitä tietojärjestelmiä. Koneoppimismallit ovat tehokkaita luokittelemaan tiedostoja joko haitallisiksi tai vaarattomiksi. Haittaohjelmat ja muut ohjelmistot kehittyvät kuitenkin jatkuvasti, minkä vuoksi luokittelijat eivät pysty oppimaan, millaisia tulevaisuuden haittaohjelmat ovat. Tästä syystä tarvitaan menetelmiä haittaohjelmissa tapahtuviin muutoksiin mukautumiseksi. Tässä opinnäytetyössä verrataan kolmea erilaista menetelmää, nimeltään retrain, threshold ja hybrid, jotka saavat luokittelijan mukautumaan ajan myötä tapahtuviin muutoksiin. Ensin työssä luodaan luokittelija, joka tunnistaa, onko Windowsin käyttöjärjestelmän suoritettava tiedosto haitallinen vai vaaraton. Luokitelijan kouluttamiseen käytetään 61466 tiedostoa, joista 19648 ovat tunnettuja haittaohjelmia ja 41818 on vaarattomia tiedostoja. Luokitteluohjelma käyttää ominaisuuksia, jotka on kerätty staattisella analyysillä tiedostoista ajamatta niitä. Luokittelijan valitsemiseksi vertaamme menetelmiä random forest, gradient boosted decision trees, neural network ja support vector machines. Parhaan tarkkuuden saavuttaa gradient boosted decision trees -menetelmää käyttävä malli, ja kouluttamiseen kuluvaa aikaa voidaan nopeuttaa käyttämällä random forest -menetelmää valitsemaan tärkeimmät ominaisuudet tiedostojen luokittelemiseksi. Tämä luokitin saavuttaa 98.7\% tarkkuuden ristiinvalidointia käytettäessä. Kun tiedostot järjestetään ajan mukaan, luokittimen tarkkuus on 96.7\%, mikä näyttää, että haittaohjelmissa tapahtuu muutoksia ajan myötä. Kukin ehdotetuista retrain, threshold ja hybrid menetelmistä parantaa luokittimen tarkkuutta. Paras menetelmä on hybrid, joka on yhdistelmä kahdesta muusta menetelmästä. Tämä menetelmä luokittelee oikein 98.5\% tiedostoista selvästi

Mining human-brain networks to discover patterns that can be used to discriminate between healthy individuals and patients affected by some neurological disorder, is a fundamental task in neuro-science. Learning simple and interpretable models is as important as mere classification accuracy. In this paper we introduce a novel approach for classifying brain networks based on extracting contrast subgraphs, i.e., a set of vertices whose induced subgraphs are dense in one class of graphs and sparse in the other. We formally define the problem and present an algorithmic solution for extracting contrast subgraphs. We then apply our method to a brain-network dataset consisting of children affected by Autism Spectrum Disorder and children Typically Developed. Our analysis confirms the interestingness of the discovered patterns, which match background knowledge in the neuro-science literature. Further analysis on other classification tasks confirm the simplicity, soundness, and high explainability of our proposal, which also exhibits superior classification accuracy, to more complex state-of-the-art methods., QC 20201217

The exponential increase in the availability of large-scale mobility data has fueled the vision of smart cities that will transform our lives. The truth is that we have just scratched the surface of the research challenges that should be tackled in order to make this vision a reality. Consequently, there is an increasing interest among different research communities (ranging from civil engineering to computer science) and industrial stakeholders in building knowledge discovery pipelines over such data sources. At the same time, this widespread data availability also raises privacy issues that must be considered by both industrial and academic stakeholders. In this paper, we provide a wide perspective on the role that big data have in reshaping cities. The paper covers the main aspects of urban data analytics, focusing on privacy issues, algorithms, applications and services, and georeferenced data from social media. In discussing these aspects, we leverage, as concrete examples and case studies of urban data science tools, the results obtained in the “City of Citizens” thematic area of the Horizon 2020 SoBigData initiative, which includes a virtual research environment with mobility datasets and urban analytics methods developed by several institutions around Europe. We conclude the paper outlining the main research challenges that urban data science has yet to address in order to help make the smart city vision a reality., QC 20201202AIP

The first Workshop on Integrity in Social Networks and Media is held in conjunction with the 13th ACM Conference on Web Search and Data Mining (WSDM) in Houston, Texas, USA. The goal of the workshop is to bring together researchers and practitioners to discuss content and interaction integrity challenges in social networks and social media platforms., QC 20200622

The problem of inconsistent planning in decision making, which leads to undesirable effects such as procrastination, has been studied in the behavioral-economics literature, and more recently in the context of computational behavioral models. Individuals, however, do not function in isolation, and successful projects most often rely on team work. Team performance does not depend only on the skills of the individual team members, but also on other collective factors, such as team spirit and cohesion. It is not an uncommon situation (for instance, experienced by the authors while working on this paper) that a hard-working individual has the capacity to give a good example to her team-mates and motivate them to work harder. In this paper we adopt the model of Kleinberg and Oren (EC'14) on time-inconsistent planning, and extend it to account for the influence of procrastination within the members of a team. Our first contribution is to model collaborative work so that the relative progress of the team members, with respect to their respective subtasks, motivates (or discourages) them to work harder. We compare the total cost of completing a team project when the team members communicate with each other about their progress, with the corresponding cost when they work in isolation. Our main result is a tight bound on the ratio of these two costs, under mild assumptions. We also show that communication can either increase or decrease the total cost. We also consider the problem of assigning subtasks to team members, with the objective of minimizing the negative effects of collaborative procrastination. We show that whereas a simple problem of forming teams of two members can be solved in polynomial time, the problem of assigning n tasks to n agents is NP-hard., QC 20210915

QC 20211001

Social media has created new ways for citizens to stay informed on societal matters and participate in political discourse. However, with its algorithmically-curated and virally-propagating content, social media has contributed further to the polarization of opinions by reinforcing users’ existing viewpoints. An emerging line of research seeks to understand how content-recommendation algorithms can be re-designed to mitigate societal polarization amplified by social-media interactions. In this paper, we study the problem of allocating seed users to opposing campaigns: by drawing on the equal-time rule of political campaigning on traditional media, our goal is to allocate seed users to campaigners with the aim to maximize the expected number of users who are co-exposed to both campaigns. We show that the problem of maximizing co-exposure is NP-hard and its objective function is neither submodular nor supermodular. However, by exploiting a connection to a submodular function that acts as a lower bound to the objective, we are able to devise a greedy algorithm with provable approximation guarantee. We further provide a scalable instantiation of our approximation algorithm by introducing a novel extension to the notion of random reverse-reachable sets for efficiently estimating the expected co-exposure. We experimentally demonstrate the quality of our proposal on real-world social networks., QC 20210906

The problem of inconsistent planning in decision making, which leads to undesirable effects such as procrastination, has been studied in the behavioral-economics literature, and more recently in the context of computational behavioral models. Individuals, however, do not function in isolation, and successful projects most often rely on team work. Team performance does not depend only on the skills of the individual team members, but also on other collective factors, such as team spirit and cohesion. It is not an uncommon situation (for instance, experienced by the authors while working on this paper) that a hard-working individual has the capacity to give a good example to her team-mates and motivate them to work harder. In this paper we adopt the model of Kleinberg and Oren (EC'14) on time-inconsistent planning, and extend it to account for the influence of procrastination within the members of a team. Our first contribution is to model collaborative work so that the relative progress of the team members, with respect to their respective subtasks, motivates (or discourages) them to work harder. We compare the total cost of completing a team project when the team members communicate with each other about their progress, with the corresponding cost when they work in isolation. Our main result is a tight bound on the ratio of these two costs, under mild assumptions. We also show that communication can either increase or decrease the total cost. We also consider the problem of assigning subtasks to team members, with the objective of minimizing the negative effects of collaborative procrastination. We show that whereas a simple problem of forming teams of two members can be solved in polynomial time, the problem of assigning n tasks to n agents is NP-hard.

The problem of inconsistent planning in decision making, which leads to undesirable effects such as procrastination, has been studied in the behavioral-economics literature, and more recently in the context of computational behavioral models. Individuals, however, do not function in isolation, and successful projects most often rely on team work. Team performance does not depend only on the skills of the individual team members, but also on other collective factors, such as team spirit and cohesion. It is not an uncommon situation (for instance, experienced by the authors while working on this paper) that a hard-working individual has the capacity to give a good example to her team-mates and motivate them to work harder. In this paper we adopt the model of Kleinberg and Oren (EC'14) on time-inconsistent planning, and extend it to account for the influence of procrastination within the members of a team. Our first contribution is to model collaborative work so that the relative progress of the team members, with respect to their respective subtasks, motivates (or discourages) them to work harder. We compare the total cost of completing a team project when the team members communicate with each other about their progress, with the corresponding cost when they work in isolation. Our main result is a tight bound on the ratio of these two costs, under mild assumptions. We also show that communication can either increase or decrease the total cost. We also consider the problem of assigning subtasks to team members, with the objective of minimizing the negative effects of collaborative procrastination. We show that whereas a simple problem of forming teams of two members can be solved in polynomial time, the problem of assigning n tasks to n agents is NP-hard.

Dynamic graphs are valuable means to represent the volatility of real-world networks. In such scenarios, dense subgraph mining is a widely studied task, as it can give insights about how the relationships change over time. However, there are cases in which these changes are correlated. For example, in a road network, a traffic accident affects also the traffic in the adjacent road segments. We consider the problem of detecting dense regions of correlation in dynamically evolving networks, and demonstrate EXCODE, a system that solves two variants of the problem, which are based on two different density measures. It enumerates all the subgraphs satisfying certain density and correlation constraints, but can also detect compact subsets of limited overlap. In this demonstration, the audience can try this tool with real-world datasets, hence visualizing, interacting, and exploring the dense correlated subgraphs discovered in the mining process. An interactive panel allows them to learn where the correlations are located in the network, how the regions of correlation are related to each other, and how they evolve over time.

When a data analyst explores data visually and observes a pattern, how can he or she determine whether the pattern is real or just a random artefact of the data? This thesis addresses the problem of evaluating visual patterns observed during visual data exploration by developing a statistical significance testing framework for visual patterns. Traditionally, patterns observed during data exploration are not evaluated with statistical testing. The reason is that any hypotheses to be tested about the data must be formulated prior to viewing the data, else there is a risk of false discoveries (Type I errors). A naive solution for combining visual exploration with statistical testing involves pre-specifying all possible hypotheses about observable patterns and then applying a multiple testing correction. However, the sheer number of potential patterns results in an overly strict multiple testing correction, resulting in low statistical power. This means that true patterns in the data may fail to be discovered, i.e., there is a risk of false negatives (Type II errors). The framework proposed in this thesis is a principled statistical significance testing procedure that controls Type I errors and is not overly conservative. The framework is based on improving statistical power by leveraging the data analyst's knowledge and by utilising multiple testing corrections that are suitable for visual exploration. An empirical investigation of the framework is performed on real and synthetic tabular data and time series, using different test statistics and null distributions. The investigation shows that the proposed framework allows the significance of visual patterns to be determined during exploratory analysis.

The aim of this work is to build a signed network from Twitter data using sentiment analysis, analyze that network, and enhance the performance of the sentiment analysis using information extracted from it. To construct the network the interactions or tweets with mentions addressing other users will be analyzed using a variant of traditional sentiment analysis known as targeted sentiment analysis. A signed network will be built between users who post a tweet and those users who are mentioned in the tweet, predicting the relationship between such users using natural language proccessing on the tweet's text. After the network is built, it will be shown that using networks similar to it, the performance of the sentiment analysis can be significantly improved. Using different approaches, the accuracy of the initial sentiment analysis model is improved by 10%.

In recent years, the social networks play an important role as the information sources for many people. The algorithms applied by these platforms feed the users with opinions that meet their tastes. These algorithms, on the other hand, harm the free flow of information by forming filter bubbles and echo chambers. The motivation of the thesis is to break filter bubbles by maximizing the diversity of opinion exposures in a social network. To achieve the goal, we assume that we can change a limited number of users’ exposures to the information in the network. We propose two concrete models, bounded-box diversity maximization and the ℓ2-bounded diversity maximization respectively. Both of them are convex maximization problems subject to different constraints. Besides the common cardinality constraint and linear constraint, the second model has an ℓ2 constraint. We give a detailed exposition of convex maximization problems under different constraints. We prove that first problem can be discretized and transformed into the Quadratic Knapsack Problem (QKP), while the second one can not. Guided by convexity and QKP, Greedy Algorithms and Semidefinite Relaxation are applied. In a high level, the core idea of the Semidefinite Relaxation consist of two components: first, relaxing the original problem into Semidefinite Programming and obtaining a solution; second, rounding the solution to a feasible solution of the original problem through sampling from a Gaussian distribution. To evaluate our problem, we implement the algorithms on datasets that have clear chambers and low diversity structure. We show that semidefinite relaxation based algorithms work well when there are large changes on the cardinality, while when the changes are small, the greedy algorithms are comparable. The greedy algorithms have descent scalability for large datasets.

Nowadays, machine learning is being applied in various domains, including safety critical areas, which directly affect our lives. These systems are so complex and rely on huge amounts of training data, so that we risk to create systems that we do not understand, which might lead to undesired behavior, such as fatal decisions, discrimination, ethnic bias, racism and others. Moreover, European Union recently adopted General Data Protection Regulation (GDPR), which requires companies to provide meaningful explanation of the logic behind decisions made by machine learning systems, if these decisions affect directly a human being. We address the issue of explaining various machine-learning models by generating counterfactuals for given data points. Counterfactual is a transformation, which shows how to alternate an input object, so that a classifier predicts a different class. Counterfactuals allow us to better understand why particular classification decisions take place. They may aid in troubleshooting a classifier and identifying biases by looking at alternations needed to be made in the data instances. For example, if a loan approval application system denies a loan for a particular person, and we can find a counterfactual indicating that we need to change the gender, or the race of a person for the loan to be approved, then we have identified bias in the model and we need to study our classifier better and retrain it to avoid such undesired behavior. In this thesis we propose a new framework to generate counterfactuals for a set of data points. The proposed framework aims to find a set of similar transformations to data points, such that those changes significantly reduce the probabilities of the target class. We argue that finding similar transformations for a set of data points helps to achieve more robust explanations to classifiers. We demonstrate our framework on 3 types of data: tabular, images and texts. We evaluate our model on both simple and real-world dat

Recommendation systems are being widely adopted for two main reasons: address the limitations of search engines in the era of Big Data, and improve the user experience by helping the user find what they want but cannot express because it is hard to state as a query or because they do not even know it exists. In the case of video-on-demand services, this can be critical to keep users engaged and avoid churn. The purpose of this project has been to develop and evaluate different recommendation algorithms to find what combination of factors can be used to simulate user behavior more accurately in a video-on-demand setting. Using the recommendation of the most popular items as a baseline, five different algorithms (with multiple parameter variations) have been tested. The results have shown that combining multiple simple models provides the best results, and that taking into consideration the context in which the recommendation is made can heavily improve the performance.

Signed networks contain edge annotations to indicate whether each interaction is friendly (positive edge) or antagonistic (negative edge). The model is simple but powerful and it can capture novel and interesting structural properties of real-world phenomena. The analysis of signed networks has many applications from modeling discussions in social media, to mining user reviews, and to recommending products in e-commerce sites. In this paper we consider the problem of discovering polarized communities in signed networks. In particular, we search for two communities (subsets of the network vertices) where within communities there are mostly positive edges while across communities there are mostly negative edges. We formulate this novel problem as a "discrete eigenvector" problem, which we show to be NP-hard. We then develop two intuitive spectral algorithms: one deterministic, and one randomized with quality guarantee $\sqrt{n}$ (where $n$ is the number of vertices in the graph), tight up to constant factors. We validate our algorithms against non-trivial baselines on real-world signed networks. Our experiments confirm that our algorithms produce higher quality solutions, are much faster and can scale to much larger networks than the baselines, and are able to detect ground-truth polarized communities.

Cycles in graphs often signify interesting processes. For example, cyclic trading patterns can indicate inefficiencies or economic dependencies in trade networks, cycles in food webs can identify fragile dependencies in ecosystems, and cycles in financial transaction networks can be an indication of money laundering. Identifying such interesting cycles, which can also be constrained to contain a given set of query nodes, although not extensively studied, is thus a problem of considerable importance. In this paper, we introduce the problem of discovering interesting cycles in graphs. We first address the problem of quantifying the extent to which a given cycle is interesting for a particular analyst. We then show that finding cycles according to this interestingness measure is related to the longest cycle and maximum mean-weight cycle problems (in the unconstrained setting) and to the maximum Steiner cycle and maximum mean Steiner cycle problems (in the constrained setting). A complexity analysis shows that finding interesting cycles is NP-hard, and is NP-hard to approximate within a constant factor in the unconstrained setting, and within a factor polynomial in the input size for the constrained setting. The latter inapproximability result implies a similar result for the maximum Steiner cycle and maximum mean Steiner cycle problems. Motivated by these hardness results, we propose a number of efficient heuristic algorithms. We verify the effectiveness of the proposed methods and demonstrate their practical utility on two real-world use cases: a food web and an international trade-network dataset., Comment: Accepted for CIKM'19

Los grafos, o redes, están compuestos por un conjunto de nodos conectados por aristas, estos nodos pueden representar distintas entidades entre las cuales hay una relación binaria representada por las aristas. Además, estas redes pueden ser usadas para modelar una gran cantidad de procesos que pueden suceder en las entidades que representan. Las redes normalmente son estáticas, no se considera su evolución respecto al tiempo. Si consideramos dicha evolución tenemos redes temporales, en las cuales las aristas solo existen en ciertos momentos temporales, los cuales pueden ser tiempos discretos o intervalos. Con esto representamos como evoluciona la relación binaria entre las entidades que forman el grafo. Esta información condiciona la definición y métodos para obtener ciertas medidas en las redes, como por ejemplo las medidas de centralidad, que representan cuanto de importante es un nodo en la red; y más especificamente, la centralidad de intermediación en los caminos más cortos ”shortest-path betweenness centrality”, en la cual un nodo se considera importante si es probable que para dos nodos aleatorios, este primer nodo se encuentre en el camino más corto entre ellos. En este trabajo comparamos los resultados para esta medida usando su definición en redes estáticas y temporales usando como red proveniente del mundo real las redes de transporte público de Madrid y de Helsinki dando como conclusión en que casos dan mayores ventajas cada modelo. Además, por último, buscamos proponer nuevos métodos que puedan suponer un compromiso entre ambos modelos o mejorarlos de alguna manera.---ABSTRACT---Graphs or networks are a set of nodes connected by edges. They can represent several different entities and pairwise relations between them. Moreover, graphs can be used to model a great number of natural and anthropogenic processes. The most common graph model is a static graph. In this kind of graphs, the nodes and edges are not modified over time. Such representation can be s

We propose a new variant of the k-median problem, where the objective function models not only the cost of assigning data points to cluster representatives, but also a penalty term for disagreement among the representatives. We motivate this novel problem by applications where we are interested in clustering data while avoiding selecting representatives that are too far from each other. For example, we may want to summarize a set of news sources, but avoid selecting ideologically-extreme articles in order to reduce polarization. To solve the proposed k-median formulation we adopt the local-search algorithm of Arya et al. We show that the algorithm provides a provable approximation guarantee, which becomes constant under an assumption on the minimum number of points for each cluster. We experimentally evaluate our problem formulation and proposed algorithm on datasets inspired by the motivating applications. In particular, we experiment with data extracted from Twitter, the US Congress voting records, and popular news sources. The results show that our objective can lead to choosing less polarized groups of representatives without significant loss in representation fidelity., Comment: The Web Conference 2019

Many 0/1 datasets have a very large number of variables; on the other hand, they are sparse and the dependency structure of the variables is simpler than the number of variables would suggest. Defining the effective dimensionality of such a dataset is a nontrivial problem. We consider the problem of defining a robust measure of dimension for 0/1 datasets, and show that the basic idea of fractal dimension can be adapted for binary data. However, as such the fractal dimension is difficult to interpret. Hence we introduce the concept of normalized fractal dimension. For a dataset $D$, its normalized fractal dimension is the number of columns in a dataset $D'$ with independent columns and having the same (unnormalized) fractal dimension as $D$. The normalized fractal dimension measures the degree of dependency structure of the data. We study the properties of the normalized fractal dimension and discuss its computation. We give empirical results on the normalized fractal dimension, comparing it against baseline measures such as PCA. We also study the relationship of the dimension of the whole dataset and the dimensions of subgroups formed by clustering. The results indicate interesting differences between and within datasets.

Online social networks are growing and becoming denser. The social connections of a given person may have very high variability: from close friends and relatives to acquaintances to people who hardly know. Inferring the strength of social ties is an important ingredient for modeling the interaction of users in a network and understanding their behavior. Furthermore, the problem has applications in computational social science, viral marketing, and people recommendation. In this paper we study the problem of inferring the strength of social ties in a given network. Our work is motivated by a recent approach [27], which leverages the strong triadic closure (STC) principle, a hypothesis rooted in social psychology [13]. To guide our inference process, in addition to the network structure, we also consider as input a collection of tight communities. Those are sets of vertices that we expect to be connected via strong ties. Such communities appear in different situations, e.g., when being part of a community implies a strong connection to one of the existing members. We consider two related problem formalizations that reflect the assumptions of our setting: small number of STC violations and strong-tie connectivity in the input communities. We show that both problem formulations are NP-hard. We also show that one problem formulation is hard to approximate, while for the second we develop an algorithm with approximation guarantee. We validate the proposed method on real-world datasets by comparing with baselines that optimize STC violations and community connectivity separately.

Finding communities in graphs is one of the most well-studied problems in data mining and social-network analysis. In many real applications, the underlying graph does not have a clear community structure. In those cases, selecting a single community turns out to be a fairly ill-posed problem, as the optimization criterion has to make a difficult choice between selecting a tight but small community or a more inclusive but sparser community. In order to avoid the problem of selecting only a single community we propose discovering a sequence of nested communities. More formally, given a graph and a starting set, our goal is to discover a sequence of communities all containing the starting set, and each community forming a denser subgraph than the next. Discovering an optimal sequence of communities is a complex optimization problem, and hence we divide it into two subproblems: 1) discover the optimal sequence for a fixed order of graph vertices, a subproblem that we can solve efficiently, and 2) find a good order. We employ a simple heuristic for discovering an order and we provide empirical and theoretical evidence that our order is good.