Models of Innovation diffusion in social networks

 

Having seen the trust modeling, centrality in social network, this post is the third and last of the series on social network analysis.

Innovation diffusion, influence propagation or ‘viral marketing’ is one of the most researched subject of contemporary era.

---

Some theory:

Compartmental models studying the spread of epidemics, which have susceptible (S), infected (I) and recovered (R) ‘SIR states’ are used to study the influence propagation in the electronic social networks as well. Initially these are descriptive models to describe a specific behavior of nodes when exposed to new innovation or information each node has an initial probability to adapt to that innovation. As each node adapts to the new innovation it has a specific amount of influence on the nodes connected to it.

Primarily two basic models are used to study the spread in a social network. An initial set of ‘active’ nodes at time t₀ exert influence on the connected nodes and at t₁ some of the connected nodes will become ‘active’ with a probability p(i). Each individual node has a threshold θ_i and when the influence from the neighbors is more than this threshold it becomes active. This model is called ‘Linear Threshold’ model. At each step, the set of nodes till the step – 1 remain active and influence their neighbors with a weightage. In independent cascade model each node is given only one chance to influence its neighbor.

---

Based on the above two diffusion models, the maximization problem is to determine the best set of initial ‘active’ nodes in a network to arrive at a best propagation by maximizing influence for ‘viral marketing’ campaign.

It is a NP-hard problem and this paper - http://pdf.aminer.org/000/472/900/maximizing_the_spread_of_influence_through_a_social_network.pdf discusses some interesting approximation algorithm with a general cascade, threshold and triggering models.

Have a good weekend reading!

On Centrality and Power in social networks

After the last weeks post on 'Trust' - http://technofunctionalconsulting.blogspot.in/2013/06/trust-modeling-in-social-media.html - let us quickly review another important measure of (social) network structure.

---

Centrality is a structural measure of a network that gives an indication of relative importance of a node in the graph / network.
Simplest way of measuring centrality is by counting the number of connections a node has. This is called 'degree centrality'.

Another way of measuring centrality is to see how far a node from all other nodes of the graph is is. This measure is called as 'closeness centrality' as it measures the path length between pairs of nodes.

'Betweenness Centrality' is the measure of number of times the node acting as a bridge on the shortest path of any other two nodes. That gives how important each n ode in connecting the whole network.

To complicate the centrality further, we have a measure called 'eigenvector centrality'. Eigenvector considers the influence for the node in the network. This methods considers the power of the nodes the current node is connected. To explain it simply, if I am connected to 500 other people on LinkedIn is different from Barak Obama connecting to 500 of his friends on the LinkedIn. His 500 connections are more influential (probably) than my 500 connections. Google's page rank is a variant of Eigenvector Centrality.

When an external factor is considered for each node and implement eigenvector centrality to consider an external α it is called 'alpha centrality'

When we move the alpha centrality measure from one node to cover multiple radii to include first degree, second degree and so on.. With a factors of β(i) and measure the centrality as a function of influence of varying degrees, it is called beta centrality.

---

The key problem with centrality computation is the amount of computing power needed to arrive at the beta centrality measure of the social network with millions of nodes. I recently came across this paper - https://www.msu.edu/~zpneal/publications/neal-alterbased.pdf which proposes an alternative approximation algorithm which is computationally efficient to estimate fairly accurate centrality measure. This alter-based non recursive method works well on non-bipartite networks and suits well for social networks.

---

Title of this blog states "power" and whole content did not mention anything about it. Generally centrality is considered as the indicator of power or influence. But in some situations power is not directly proportional to centrality. Think about it.

Trust modeling in social media

 

After last week’s “tie strength” post, this week let me give some fundamentals on importance of modeling TRUST in social media.

What is Trust?
It is difficult to define. But when I ask “Will you loan a moderate amount to the other person?” or “Will you seek a reference or recommendation regarding a key decision?” help understand the term TRUST.

There are two components to TRUST. Some people are more trusting than others. Some quickly establish trust where as others take a long time in establishing the trust. This component is not easy to be modeled. The second component is the credibility of the trusted person.

Measuring Trust:
In social media, the second component can be measured by analyzing the sentiment based on the blogs referenced by others. This is called “network based trust inference”.

This paper http://ebiquity.umbc.edu/_file_directory_/papers/375.pdf describes a model for measuring trust using link polarity.

Have a good weekend reading!

"tie strength" in social media

What is "tie strength”?

When analyzing the social web, we see various edges (ties or relationships) connecting the nodes (individuals or organizations). Theoretically the strength of the edge or relationship is categorized as strong or weak. In 1973 paper titled "The strength of weak ties" - http://sociology.stanford.edu/people/mgranovetter/documents/granstrengthweakties.pdf  Mark Granovetter lays foundations of importance of strength of ties in micro and macro levels of sociology.

---

Predictive model
Recently I came across a predictive model developed using Facebook which considers seven dimensions of "tie strength" They are: Intensity, Intimacy, Duration, Reciprocal Services, Structural, Emotional Support and Social Distance.

32 Predictive variables from Facebook interactions have been used along with a survey deriving 5 dependent variables that fits into the predictive model.
The model uses statistical linier method to predict the strength of a relationship in continuous 0 - 1 Scale.

More on - http://social.cs.uiuc.edu/people/gilbert/pub/chi09-tie-gilbert.pdf

I like the methodology used and practical approach towards predictive modelling. More stronger the tie, better influence....

Data Philosophers and data quality

After data scientists and data artists, another need is for "data philosophers”.
http://www.ocdqblog.com/home/the-need-for-data-philosophers.html made me think about the data philosophers.

So, the data scientists are focusing on the underlying technology to gather validate and process the 'big' data and the artists are using the processed 'big' data to paint and visualize the insights.

In this whole process due to its wide variety and velocity (two 'V's of big data!) are we missing on the rigor of quality of data?

Considering the 36 attributes of data quality in the 1972 paper of Kristo Ivanov - http://www8.informatik.umu.se/~kivanov/diss-avh.html and evaluating today's big data insights, I somehow feel there is a 'big' gap in the quality of 'big data'.

I see some parallels in big data processing and orbit determination. As long as the key laws governing the planetary motion are unknown, whatever is the amount of the data from observation we have, we will not be able to explain the ‘retrograde motion’ of the planets. In the same way, if we do not have a clear understanding of underlying principles of the data streams, we will not be able to explain them. That is where we need the philosophers!

Now, I think I am becoming a “Data Philosopher” already!

Data Artist - A new professional skillset?

In past few days, I have seen at least two blogs talking about "Data Artist"

1. http://www.thetibcoblog.com/2013/05/04/forget-being-a-data-scientist-and-become-a-data-artist/
2. http://www.datasciencecentral.com/profiles/blogs/the-rise-of-the-data-artist-in-business

The trend seems to go towards business centric data visualization of so called "big data".

Definition:
One who can use data as the paint and create art that can represent massive flows of data and visualize the patterns in a way business users are delivered with a lot of “information” in a single glance.

---

It is slightly different from the “Data Scientist” profession. Data Scientists are focused on technical process of collecting, preparing and analyzing the data for patterns where as the Data Artists specialize in visualizing the discoveries in an artistic manner!

"Scientific Artists" and "Artistic Scientists" with Data! Are we complicating the matter too much??

All (that I know) about Exadata

Having associated with Exadata in one or other way from its release ( see: http://technofunctionalconsulting.blogspot.in/2008/09/exadata-database-processing-moves-into.html ) I have tried consolidating key points related to Exadata for a session to technical audience.


Related Posts: 

http://technofunctionalconsulting.blogspot.in/2009/10/exadata-v2-worlds-first-oltp-database.html

http://technofunctionalconsulting.blogspot.in/2010/02/hybrid-columnar-compression-hcc.html

http://technofunctionalconsulting.blogspot.in/2012/06/exadata-performance-features.html

Accelerating Analytics using “Blink” aka “BLU acceleration”

This Friday marks completion of my 2 years in the second innings with TCS ‘s Technology Excellence Group and it is time for a technical blog post.

During this week, I have seen IBM announcing new “BLU acceleration” enabled DB2 10.5 that claims a 10 to 20 times performance improvement out of box.  (Ref: http://ibmdatamag.com/2013/04/super-analytics-super-easy/ )

This post aims at giving a brief summary of the Blink Project which has brought in this acceleration to the analytic queries.

The Blink technology has primarily two components that achieve the said acceleration to the analytic processing:

1.       The compression at the load time

2.       The query processing

Compression & Storage:

At load time each column is compressed using a “Frequency Partitioning” order preserving fixed length dictionary encoding method. Each partition of the column has a dictionary of its own making it to use shorter column codes. As it preserves order the comparison operators/predicates can be applied directly to the encoded values without needing to uncompress them.

Rows of are packed using the bit aligned columns to a byte aligned banks of 8, 16, 32 or 64bits for efficient ALU operations. This bank-major storage is combined to form blocks that are then loaded into the memory (or storage.) This bank-major storage exploits SIMD (Single Instruction, Multiple Data) capability of modern POWER processor chips of IBM.

Query Processing:

In Blink there are no indexes, no materialized views nor a run-time query optimizer. So, it is simple. But the query must be compiled to take care of different encoded column lengths of each horizontal partition of the data.

Each SQL is split into a series of single-table queries (STQs) which does scans with filtering. All the joins are hash joins. These scans happen in an outside-in fashion on a typical snowflake schema creating intermediate hybrid STQs.

Blink executes these STQs in multiple blocks to threads each running on a processor core. As most modern ALUs can operate on 128bit registers all the operations are bit operations exploiting SIMD which makes the processing fast.

For more technical details of Blink project refer to - http://sites.computer.org/debull/A12mar/blink.pdf

Hope this will bring “Analytics” a boost and some competition to Oracle’s Exa- appliances. Views, Comments?

Can we save capitalism from itself?

Thoughts from reading
The Trouble With Markets: Saving Capitalism from Itself, Second Edition
by  Roger Bootle

---

This book has three sections and the Economist author goes on to say how we have ended up here in the first three chapters.  

Section 1: The great implosion:
The 1930s had seen the Great Depression and the 1970s the Great Inflation. The 1990s had seen the Great Moderation. This was the Great Implosion.
The next 4 chapters he deals with the trouble with the markets.
 
Section 2: The trouble with the Markets
As Robert Heilbroner put it: “The profit motive, we are constantly being told, is as old as man himself. But it is not. The profit motive as we know it is only as old as modern man.”
OK, The next section of three chapters
 
Section 3: From implosion to Recovery
Keynes was right in three major respects:

• Economic activity is permeated by fundamental uncertainty.
• As a result, many of the major factors that affect the economy are psychological and depend critically on the state of confidence, which is not readily analyzable or predictable.
• Consequently, the modern economy is inherently unstable and fragile

Conclusion:
Conclusion starts with this quote -
All happy families are alike; each unhappy family is unhappy in its own way.
--Leo Tolstoy, 1873

---

 

Overall this book is a good read, but I am still unsure of one thing:
So, Is it really possible to save capitalism from itself?

De-normalizing with join materialized views fast refresh on commit

Background:
Two weeks back, I wrote a post on result_cache feature of Oracle 11g database to solve a specific performance scenario in MDM implementation. Working on the same set of performance issues, we have encountered another situation where we have a normalized structure which results in writing queries to use OUTER JOINS to achieve the required aggregation.

Problem:
The structure contains a set of tables for PERSON and another set of tables to represent ORGANIZATION when a CUSTOMER can be a PERSON or an ORGANIZATION.
The requirement is to get a consolidated view of all persons and organizations together with certain attributes. We need to perform a UNION ALL query joining a total of 8 tables that is going to result in something like 10Million records. We will not be able to result_cache this result in memory.

Solution:
Inevitably we need to create a persistent version of the result of the UNION ALL query in a materialized view. But customer needs real-time data and can’t afford any latency. So, we need a view that gets updated whenever underlying tables change. That is where the “REFRESH FAST ON COMMIT” comes into the picture.
To be able to do fast refresh MATERIALIZED VIEW LOG to be created on all the underlying tables. We have selected “rowid”. All the 8 underlying tables need to have the MV LOGS created before creating a MV as follows:

CREATE MATERIALIZED VIEW MV_PN_ORG REFRESH FAST
WITH rowid ON COMMIT AS
SELECT < REQUIRED COLUMNS>
  p.rowid  AS prowid,
  xp.rowid  AS xprowid,
  xpn.rowid AS xpnrowid,
  pn.rowid  AS pnrowid
FROM person p,
  xperson xp,
  xpersonname xpn,
  personname pn
WHERE p.PID  = xp.XPid
AND XPN.XPID = PN.PNID
AND pn.CId  = p.CId
AND xpn.preferred_ind  ='Y'
UNION ALL
SELECT <REQUIRED COLUMNS>,
  o.rowid  AS orowid,
  xo.rowid  AS xorowid,
  xon.rowid  AS xonrowid ,
  orgn.rowid AS orgnrowid
FROM org o,
  xorg xo,
  xorgname xon,
  orgname orgn
WHERE o.cid  = xo.xoid
AND xon.xON_id =orgn.ONid
AND orgn.cId  = o.Cid
AND xon.preferred_ind  ='Y';

This MV now has de-normalized data which can be used in the higher level queries for looking up requird data without costly joins. We can also create INDEXes on the MV to improve lookup.

Any experiences? (both good and bad are welcome for discussion)