Tag Info

17

This is known as majority dynamics. Usually the assumption is that all nodes adopt the majority opinion simultaneously, and this is known as the synchronous model. For an arbitrary tie-breaking rule, this converges either to a fixed point or to a cycle of length 2; see for example pages 5-6 of Ginosar and Holzman's The majority action on in nite graphs: ...

11

What you're looking for is a heuristic. No algorithm can say, given a graph of friends as the only input, whether two individuals not directly connected are friends or aren't; the friendship/acquaintance relation isn't guaranteed to be transitive (we can assume symmetry, but that might even be a stretch in real life). Any good heuristic will therefore need ...

10

There is a lot of work done on this problem as the popularity of social networking has taken off. The problem is typically termed "Link Prediction" and very good and comprehensive surveys can be found here and here. The methods range from the very simple (e.g. Jaccard similarity between nodes) to the very complex (e.g. constructing statistical models of the ...

7

You can think of the social graph as a matrix $\mathbf{M}$. One approach to the problem is to first calculate $\mathbf{M}^2$, which will give all of the paths of length two between two actors in the social network. This can be seen as the weight of the connection between these friends of friends. The next step is to select the columns from the row of $\... 6 This is not generally achievable. Consider a blue and a red triangle connected with a single edge. Whatever node you select will keep its previous colour. In general, if you have large monochromatic clusters with few connections between them, the graph is stable. 5 You're (basically) computing the square of the graph, in which two vertices are adjacent if there is a path of length 2 (or at most 2, depending on the definition) connecting them. The square will contain at least two connected components, corresponding to the two bipartitions. 4 The interests are categorical data and may be modeled as binary variables (a user either likes them or he does not). You can subsume little-used categories under broader categories. For example, a user who likes a little-known horror movie can simply be marked as liking horror movies. You can even subsume such items under multiple categories if it belongs to ... 4 Disclaimer: I am wildly guessing here; I have not read any genre research. You could look at how many connections to nodes share relatively to the number of conncetions a node has. This is a very naive (as local) idea, but here goes. Every node$N$(person or some other concept) has a set of connections$C_N$. Now, given two nodes$N_1$and$N_2$, suggest$...

4

There was a presentation on ICSE 2011, at the New Ideas and Emerging Results track, entitled "How do programmers ask and answer questions on the web?". They only had initial results, but they sounded very interesting and promising. Maybe you could contact the authors if you need more info (they're from the Dept. of Comput. Science, University of Victoria, ...

3

Suppose we want to quantify the extent to which $v$ is between $s$ and $t$. There could be a few ways. One way to describe that extent is the probability of passing through $v$ if we want to reach from $s$ to $t$ by a randomly-selected shortest path. Assuming each shortest path is selected with equal probability, we will get $\frac{\sigma_{st}(v)}{\sigma_{... 3 However it doesn't seem to me that the formula calculates what is defined. The formula is right. The betweenness centrality is a value in an interval$[0, \ldots, 1]$. Thus, if the betweenness centrality of node$v$is equal to$1$, then all shortest paths between two nodes of this graph pass through$v$. I will explain the correctness of this summation ... 3 Okay, this is my approach to this problem. I think the key concept here is the clustering coefficient$c$. The value of$c$is denotes how likely it is that two nodes are connected by an edge, if the have a common neighbor. In SN-friendship graphs the clustering coefficient is usually high compared to classical random graph models, such as Erdös-Rényi. What ... 3 My metric of choice would be the communication by direct message. However, this metric is hard to come by since measuring it requires the user's consent. I do not think that using similar hashtags or terms has any say over friendship. People tend to adjust to the language they read and do not require personal bonding to do so. I think mentions are a good ... 3 The conference paper "StackOverflow and GitHub: associations between software development and crowdsourced knowledge" looked at the correlation between activity on StackOverflow and GitHub for users who have accounts on both. From the abstract: In this paper we investigate the interplay between StackOverflow activities and the development process, ... 3 You may want to have a look at the block two-level Erdos-Renyi model (BTER). The usual preferential attachment mechanism for generating scale-free networks doesn't capture the clustering coefficient right, and small-world networks aren't scale-free; the BTER model can capture both scale-free and clustering behavior. I think they have some way to make it work ... 3 If you want to find cliques, or quasi-cliques, don't expect non-overlapping communities, as their definitions imply that there might be overlap between clusters. When it comes to community detection or clustering, you need to make a formal definition of a community or cluster (in this case it is a clique). There are two types of definitions: Non-... 3 yes, social networks have a simple (graph) connectivity property in many or most cases/ situations/ contexts (such as "friend" connections on a social network like Facebook etc), but also a weighted property of the graph in various other situations. a common aspect of this now measured is widely/ generally referred to as the influence of the "friendship". ... 3 For your first question, an empty graph becomes connected roughly when$n\log n$random edges are inserted into it, in a way quantified in Erdős and Rényi's fundamental paper On the evolution of random graphs, and recounted in textbooks on random graphs. Your second question is not stated precisely and so is difficult to answer. 2 Simulating random graphs with tunable clustering is non-trivial. One method is that described by Newman. As you say there are various (conflicting) definitions of 'clustering coefficient'. Check the paper and see if it corresponds to yours. In any case you will need to compute an appropriate 'triangle corner' distribution. Then to simulate the graph with ... 2 As far as I know, clustering coefficient determines the degree to which nodes in the graph tend to cluster together, and the degree shows how individuals behave for choosing their neighbors. I usually use GTgraph to generate random graphs. You may use Erdos-Reyni graphs if the degree distribution matters or use SSCA graphs if you are looking for cliques and ... 2 While the algorithm doesn't know the graph, when you are analyzing the performance of the algorithm on a graph, you do know the graph. For a similar example, take the egg dropping puzzle. In this puzzle, the algorithm doesn't know the value of$T$, but when analyzing the algorithm, you are allowed to use the value of$T$; indeed, otherwise it's not clear ... 2 Sure, of course. You can define a matrix to contain whatever numbers you want it to contain. There's nothing that prevents you. The real question is whether the result has the properties you want it to have, but since you haven't listed any properties, there's nothing to answer here. 2 Another heuristic idea: Find a long shortest path, and pick the vertex halfway along it. Pick a vertex and run BFS from it. For some small$k$, take the$k$furthest vertices from the original vertex that the BFS determines, and repeat the process on each of them, keeping the$k$overall furthest vertices each time. Repeat a few times. If the graph is a ... 1 After a bit of reading through literature I've come upon "closeness centrality" which is the reciprocal of what I'm calculating (mean distance, which they call "farness" in the article). But I still haven't found any algorithms for finding the "closeness center" (node with maximum closeness centrality) that is faster than$O(N^2)$. As a heuristic, I have ... 1 Certainly it is possible. For example, in the following study the Indian railway network was analyzed. Small-world properties of the Indian railway network. Parongama Sen, Subinay Dasgupta, Arnab Chatterjee, P. A. Sreeram, G. Mukherjee, and S. S. Manna. Phys. Rev. E 67, 036106 – 2003 In another study, the Chinese railway network was considered. W. Li, ... 1 Assuming for the moment that the two types of person are distinct, your graph is (directed) bipartite, so it makes more sense to store it as a matrix whose rows correspond to people with fishing rights, and whose columns correspond to fishermen. If a person can function in both roles, you can think of their two personas as distinct, i.e., have a row and a ... 1 The problem can be reduced to finding "sources" (opposite of "sinks", nodes with in-degree zero) in the graph. Suppose there is an optimal solution in which$B$is one of the chosen nodes and there is an edge$A\rightarrow B$. Then we can put$A$instead of$B$in the solution and still cover the whole graph ($A$can reach$B\$, so it can reach all the nodes ...

1

What you want to do is make some form of graph. Your nodes could be users on Twitter, or posts, actions, etc. I would recommend a weighted digraph with multiple edges allowed (though you could just represent this by summing the weights of multiple edges). You want your edges to be something which indicates a link between these two people, such as mentioning ...

Only top voted, non community-wiki answers of a minimum length are eligible